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'

Answer 4

如果这不仅仅是一个家庭作业问题，并且您实际上是为了某个更大的目标而尝试反转字符串，那么只需执行 s[::-1] 即可。

Answer 5

def reverse_string(s):
    if s: return s[-1] + reverse_string(s[0:-1])
    else: return s

或者

def reverse_string(s):
    return s[-1] + reverse_string(s[0:-1]) if s else s

Answer 6

我知道现在回答原来的问题已经太晚了，这里已经回答了多种更好的方法。我的答案是出于文档目的，以防有人试图实现字符串反转的尾递归。

def tail_rev(in_string,rev_string):
    if in_string=='':
        return rev_string
    else:
        rev_string+=in_string[-1]
        return tail_rev(in_string[:-1],rev_string)
    
in_string=input("Enter String: ")
rev_string=tail_rev(in_string,'')
print(f"Reverse of {in_string} is {rev_string}") 

Answer 7

如果您不想返回响应，可以使用此解决方案。这个问题是 LeetCode 的一部分。

class Solution:
    i = 0
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        if self.i >= (len(s)//2):
            return
        s[self.i], s[len(s)-self.i-1] = s[len(s)-self.i-1], s[self.i]
        self.i += 1
        self.reverseString(s)

Answer 8

s = input("Enter your string: ")

def rev(s):
    if len(s) == 1:
        print(s[0])
        exit()
    else:
        #print the last char in string
        #end="" prints all chars in string on same line
        print(s[-1], end="")
        """Next line replaces whole string with same
         string, but with 1 char less"""
        return rev(s.replace(s, s[:-1]))

rev(s)