使用递归连接两个字符串

Question

我的目标是使用递归连接两个字符串。

输入为 str1 = ("long string") str2 = ("yes so long")

输出为：'lyoensg ssto rlionngg'

假设两个字符串的长度相同。

我现在的代码是：

def concat_order(str1, str2):
    if len(str1) == 0:
        return 'complete'
    i = 0
    new_str = str1[i] + str2[i]
    i = i + 1
    return concat_order(str1[1:], str2[1:])
    return new_str
print(concat_order("long string"', "yes so long"))

我确定我离得很近，但我正在努力让它循环。

我不能使用循环，但我可以使用 if 语句

Answer 1

递归只需要一个基本案例和一个递归案例。在这里，您的基本情况有点奇怪。你永远不需要字符串 "complete" 所以你不应该 return 那个。 str1 为空时的基本情况应该只是 return 空字符串。

然后你只需要从每个字符串中取出第一个字母，concat，然后用递归的方式连接剩下的：

def concat_order(str1, str2):
    if len(str1) == 0:
        return ''
    
    a, b = str1[0], str2[0]
    
    return a + b + concat_order(str1[1:], str2[1:])
   

concat_order("long string", "yes so long")
# 'lyoensg  ssot rlionngg'

请注意额外的 space 是正确的行为，除非需要阻止它们。

Answer 2

def concat_strings_rec(str1, str2):
    if len(str1) < 1:
        return ""
    else:
        curStr = str1[0] + str2[0]
        return curStr + concat_strings_rec(str1[1:], str2[1:])


def concat_string_iter(str1, str2):
    return "".join([str1[i] + str2[i] for i in range(len(str1))])


string1 = "long string"
string2 = "yes so long"

print(concat_strings_rec(string1, string2))
print(concat_string_iter(string1, string2))

预期输出：

lyoensg  ssot rlionngg
lyoensg  ssot rlionngg

递归求解

您需要数组长度为 0 的基本情况。在这种情况下 return 一个空字符串。在所有其他情况下 return 每个字符串的第一个元素与递归调用 concat_strings_rec() 的 return 值连接。请记住减小递归调用的数组大小！

迭代求解

迭代解决方案只是遍历数组，连接两个字符串中的每个字符，并将连接的第一个、第二个、第三个……字符放入一个数组中。然后使用"".join()将数组中的这两个字符串拼接成一个完整的字符串。

推荐

不要使用递归解决方案，因为它只会因调用堆栈而消耗更多内存，而且速度会变慢，而且由于 Python 对调用堆栈上的调用次数有限制，因此它会失败对于更大的字符串。

Answer 3

您不需要像这样传递 'i'：new_str = str1[i] + str2[i] 因为您已经 returning 字符串不包括前一个字符：return concat_order(str1[1:], str2[1:]).

另外一个函数不能有两个这样的return语句：

    return concat_order(str1[1:], str2[1:])
    return new_str

return 语句之后的任何语句都不会执行。这就是为什么我们在一些条件语句中写多个 return 语句，比如 if else

已修改您的程序以给出正确答案。

def concat_order(str1, str2, new_str):
    if len(str1) == 0:
        return new_str
    new_str += str1[0] + str2[0]

    return concat_order(str1[1:], str2[1:], new_str)

ans = ""
print(concat_order("long string", "yes so long", ans))

或者您可以这样做：

def concat_order(str1, str2):
    if len(str1) == 0:
        return ''
        
    return str1[0] + str2[0] + concat_order(str1[1:], str2[1:])

print(concat_order("long string", "yes so long"))

当控制流达到基本情况时，我们已经有了我们想要的，所以不要 return 任何东西。

使用递归连接两个字符串

Using recursion to concatenate two strings

python

string

recursion

if-statement

concatenation

递归求解

迭代求解

推荐