Python使用递归来反转字符串

Question

我想使用递归来反转python中的字符串,以便向后显示字符(即"Hello"将变为"olleh"/"olle h".

我写了一个迭代地做的:

def Reverse( s ):
    result = ""
    n = 0
    start = 0
    while ( s[n:] != "" ):
        while ( s[n:] != "" and s[n] != ' ' ):
            n = n + 1
            result = s[ start: n ] + " " + result
            start = n
    return result

但是我究竟如何递归地做到这一点呢？我对此部分感到困惑,特别是因为我不使用python和递归.

任何帮助,将不胜感激.

Answer 1

def rreverse(s):
    if s == "":
        return s
    else:
        return rreverse(s[1:]) + s[0]

(很少有人在Python中进行繁重的递归处理,语言不是为它而设计的.)

Answer 2

为了递归地解决问题,找到一个易于解决的简单案例,并通过将问题分解为更简单和更简单的版本来弄清楚如何处理这个简单的案例.

你在倒转字符串时做的第一件事是什么？从字面上看第一件事？你得到字符串的最后一个字符,对吧？

因此,一个字符串的反向是最后一个字符,然后一切的反向,但最后一个字符,这哪里是递归的用武之地.字符串的最后一个字符可以被写成x[-1],而一切,但最后一个字符x[:-1].

现在,你如何"走出低谷"？也就是说,如果没有递归,你能解决的琐碎案例是什么？一个答案是单字符串,它是相同的正向和反向.所以,如果你得到一个单字符串,你就完成了.

但是空字符串更加微不足道,有人可能会将其传递给您的函数,因此我们应该使用它.毕竟,一个字符的字符串也可以分解为最后一个字符和除最后一个字符之外的所有字符; 只是除了最后一个字符之外的所有字符都是空字符串.因此,如果我们通过返回它来处理空字符串,我们就设置了.

把它们放在一起,你得到:

def backward(text):
    if text == "":
        return text
    else:
        return text[-1] + backward(text[:-1])

或者在一行中:

backward = lambda t: t[-1] + backward(t[:-1]) if t else t

正如其他人所指出的,这不是你通常在Python中这样做的方式.迭代解决方案会更快,使用切片来实现它会更快.

此外,Python对堆栈大小施加了限制,并且没有尾调用优化,因此递归解决方案仅限于反转大约一千个字符的字符串.您可以增加Python的堆栈大小,但仍然存在固定限制,而其他解决方案始终可以处理任意长度的字符串.

Answer 3

我只想根据Fred Foo 的回答添加一些解释。假设我们有一个名为 'abc' 的字符串，我们想返回它的反向字符串，它应该是 'cba'。

def reverse(s):
    if s == "":
        return s
    else:
        return reverse(s[1:]) + s[0]
   
             
s = "abc"
print (reverse(s)) 

这段代码的工作原理是：当我们调用函数时

reverse('abc')                       #s = abc
=reverse('bc') + 'a'                 #s[1:] = bc    s[0] = a
=reverse('c') + 'b' + 'a'            #s[1:] = c     s[0] = a
=reverse('') + 'c' + 'b' + 'a'
='cba'