CODEWITHSUNDEEP
pythonstringrecursion
Charlie Baker
Charlie Baker

Reputation: 81

Explanation for reverse_string recursive function

No matter how many times I run it by Python visualizer, I can't figure out how this code works; can someone PLEASE tell me how the recursion of this following code works?

def reverse_strings(string):
    if len(string) == 0: return ''
    else: return reverse_strings(string[1:]) + string[0]

reverse_strings('hello')

I wrote it myself, and it works, but I have no idea how it works. I know return recursion works by running the "ello" into the recursive function, but I can't for the life of me understand how it's printing things backwards.

Upvotes: 0

Views: 190

Answers (4)

Jim Witschey
Jim Witschey

Reputation: 285

To really understand this, I would express it in a declarative, sort-of logical form. Here's your code:

1: if len(string) == 0: return ''
2: else: return reverse_strings(string[1:]) + string[0]

I'll call the first element of a string (string[0]) its head and the remainder (string[1:]) its tail. If a string is only 1 character long, we consider its tail to be the empty string. In terms of that vocabulary, here are the rules for what it means to reverse a string:

  1. The empty string reversed is the empty string.
  2. Any other string reversed is the reversed version of its tail, followed by its head.

In the case of, for example, abcd, we apply rule 2 since rule 1 doesn't apply:

  • abcd reversed is bcd reversed, followed by a.

Ok, what's bcd reversed? Well, we can apply the same rule:

  • bcd reversed is cd reversed, followed by b.

and down the chain:

  • cd reversed is d reversed, followed by c,
  • d reversed is '' reversed, followed by d,
  • '' reversed is '', by rule 1, because it is the empty string.

Going back up this list, you get:

  • '' followed by d followed by c followed by b followed by a

which is dcba, which is what we wanted!

Wrapping your head around recursion isn't easy. Try to solve some other problems with it or do some exercises that require it; this kind of practice really helps understanding.

Upvotes: 0

nbro
nbro

Reputation: 15837

The concept of recursion is that you call a the same function until the base case is encountered. In your case, the base case is when len(string) == 0, where you return an empty string to the caller, which was a previous version of the same function reverse_strings, but with different parameters (usually a more "complex" function).

Suppose you have this simple string hi, your function would behave like this:

  1. Check if the base case is reached, if yes, return an empty string, otherwise go to next statement. Since we don't have an empty string, we go to the next statement.

  2. Next statement calls the same function reverse_strings, but with different parameters than when you call it the first time to run it; in fact, the first time you call it, you do something like this reverse_strings('hi'). In the else, you are calling the function with a smaller version of your string hi, observe in the following statement: return reverse_strings(string[1:]) + string[0] that string[1:] is just i. Now, basically you have return reverse_strings('i') + string[0]. Note that string[0] is H. Here, reverse_strings('i'), as I said above, you are calling your function again, but with a smaller version of your string i.

  3. Now, we are inside another function call. The first statement if len(string) == 0: return '' is evaluated. Is it true? No, because len(string) is still different from 0. So we pass to the next statement else: return reverse_strings(string[1:]) + string[0]. Now, note that we are going to call the same function again. but with a smaller string, in this case, an empty string, since string[1:] of i is an empty string. So our call can be summarised like this return reverse_strings('') + i.

  4. We are now in another "simplified version" of reverse_strings. The first statement is evaluated if len(string) == 0: return ''. Is it true? Yes, because, remember, our string is now an empty string. What happens now is that you return an empty string to the caller, which is the function in the point 3.

  5. Now, we have just returned an empty string to the caller at point 3, so we have return '' + i. '' + i is nothing else than simply i, which you are going to return to the caller of this function at pointer 3, which is the function at point 2.

  6. Now, you have just returned i to the caller, specifically you have just returned i to this statement return reverse_strings('i') + string[0], where string[0] is H and reverse_strings('i') is just i that you have just returned. So, now you have iH, and you have just reversed the string.

Upvotes: 1

Padraic Cunningham
Padraic Cunningham

Reputation: 180391

string[1:] on the first call is ello string[0] is h:

2nd recursive call string[1:] -> llo string[0] -> e

3rd string[1:] ->lo string[0] -> l

4th string[1:] ->o string[0] -> l

5th string[1:] ->"" string[0] -> o

So reverse_strings(string[1:]) calls the function recursively moving across the string and string[0] concatenates each letter starting from the end which is what is returned at the end.

The graph below may help:

recursion tree

Upvotes: 0

Cory Kramer
Cory Kramer

Reputation: 117856

It uses slicing to concatenate the first letter onto the end, then pass the 2nd to remaining letters into the recursive function again.

Upvotes: 0

Related Questions