Python reversing a string using recursion

Question

I want to use recursion to reverse a string in python so it displays the characters backwards (i.e "Hello" will become "olleh"/"o l l e h".

I wrote one that does it iteratively:

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

But how exactly do I do this recursively? I am confused on this part, especially because I don't work with python and recursion much.

Any help would be appreciated.

Answer 1

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

(Very few people do heavy recursive processing in Python, the language wasn't designed for it.)

Answer 2

To solve a problem recursively, find a trivial case that is easy to solve, and figure out how to get to that trivial case by breaking the problem down into simpler and simpler versions of itself.

What is the first thing you do in reversing a string? Literally the first thing? You get the last character of the string, right?

So the reverse of a string is the last character, followed by the reverse of everything but the last character, which is where the recursion comes in. The last character of a string can be written as x[-1] while everything but the last character is x[:-1].

Now, how do you "bottom out"? That is, what is the trivial case you can solve without recursion? One answer is the one-character string, which is the same forward and reversed. So if you get a one-character string, you are done.

But the empty string is even more trivial, and someone might actually pass that in to your function, so we should probably use that instead. A one-character string can, after all, also be broken down into the last character and everything but the last character; it's just that everything but the last character is the empty string. So if we handle the empty string by just returning it, we're set.

Put it all together and you get:

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

Or in one line:

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

As others have pointed out, this is not the way you would usually do this in Python. An iterative solution is going to be faster, and using slicing to do it is going to be faster still.

Additionally, Python imposes a limit on stack size, and there's no tail call optimization, so a recursive solution would be limited to reversing strings of only about a thousand characters. You can increase Python's stack size, but there would still be a fixed limit, while other solutions can always handle a string of any length.

Answer 3

I just want to add some explanations based on Fred Foo's answer. Let's say we have a string called 'abc', and we want to return its reverse which should be 'cba'.

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

How this code works is that: when we call the function

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

If this isn't just a homework question and you're actually trying to reverse a string for some greater goal, just do s[::-1].

Answer 5

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

or

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

Answer 6

I know it's too late to answer original question and there are multiple better ways which are answered here already. My answer is for documentation purpose in case someone is trying to implement tail recursion for string reversal.

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

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)

Answer 8

if you do not want to return response than you can use this solution. This question is part of 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)