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.

Solution 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.)

Solution 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.

Solution 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'

Solution 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].

Solution 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

View more solutions

Comments

[intuited]

Fun fact: This is sometimes referred to as a "Martian smiley".

[Eric]

Ok that works but how exactly does the bottom part work? You are calling the function rreverse on the 1st element of string and printing out the 0th element out. How exactly does the rreverse(s[1:]) get incremented each time?

[Asterisk]

@Eric recursive call is made on the substring of s starting from the second element (e.g S[1:] gives you s without the first element). He is then appending the result of the recursive call to the first character of s, e.g. s[0].

[kindall]

reversed() doesn't do what you think it does. :-)

[High schooler]

^ w0w at least explain

[GL2014]

^ Maybe you should at least try it yourself? ''.join( [i for i in reversed(s)]) does what you think it does, reversed returns a reversed object which you must iterate over to get back a string.

[Moniba]

The question specifically says they want to use "recursion" to solve the problem.