Understanding how stack frames work in recursive function

Question

Python/CS newbie here, trying to understand how a particular recursive function works "under the hood" in terms of how the function's stack frames are operating and what values they're "holding."

I know a lot has been written/posted about recursive functions on here, and there are illustrative examples of how they work, but the concepts of recursion and how stacks work/what they do in a recursive function are a little tricky and I'm not finding any clear and concise explanations.

Let's say we have the following recursive function that reverses the characters in a string:

text = "hello"
def reverse_string(text):
        if len(text) <= 1:
            return text
        return reverse_string(text[1:]) + text[0]

which outputs: olleh

I'm thinking that the frames for the reverse_string(text[1:]) work as follows:

Global frame
text    "hello"
reverse_string  

reverse_string
text    "hello"

reverse_string
text    "ello"

reverse_string
text    "llo"

reverse_string
text    "lo"

reverse_string
text    "o"

Return
value   "o"

But what happens after the value "o" is returned and the terminating base condition is met? How does text[0] work in the function to finally arrive at "olleh" ?

Tr1gZer0 Tr1gZer0 · Accepted Answer · 2015-06-03T03:24:59

Just taking your example for a walk.

Once we reach the terminating condition, the remaining frames are pop'd in reverse order.

Suppose we reach the terminating condition in which case return text is "hit" and text = "o" is returned. Then in the previous frame we have reverse_string(text[1:]) + text[0] but this is just reverse_string("o") + "l" = "o" + "l" = "ol" = reverse_string(text[1:]), where reverse_string(text[1:]) is the call from the previous frame (the one for which text was equal to "llo"). Continuing this logic, reverse_string("lo") + "l" = "ol" + "l" = "oll".

We continue this same idea until we reach the "top" frame where we finally return "olleh".

Understanding how stack frames work in recursive function

1 Answers