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.