The Call Stack

A Puzzle

Here is a rather puzzling case of recursion. The code seems fine, but I still run into problems!

def my_length(some_list, number):
    return number if some_list == [] else my_length(some_list[1:], number+1)

It has a base case that occurs when some_list is an empty list, so there shouldn’t be infinite recursion. With every recursive call, the slice notation drops the zeroeth element of the list, so it is in fact becoming a smaller list every time.

And it seems to in fact work.

>>> b = [0] * 10
>>> print my_length(b, 0)

Everything’s perfect, right? Hmm, not quite!

>>> b = [0] * 1000
>>> print my_length(b, 0)
RuntimeError: maximum recursion depth exceeded in cmp

Uh oh. What went wrong? I thought RuntimeError: maximum recursion depth exceeded only occurred infinite recursion cases.

Not quite. To get to the bottom of why this happens, we need to understand how recursion works.

Stack Frame

For the purposes of this class, there are two places data can live:

Global variables live in a zone called, confusingly, “data”. Great. But what lives in the stack? Each function call (or method call) gets one box on the stack. More importantly, these boxes are independent – one function doesn’t get to access a different function’s box. These “boxes” are called stack frames.

So what is inside a stack frame? There are a few things that we care about in this class, and each of your stack frame drawings will have to emulate this.

So let’s look at the file

a = 5
print a
print "Wow, no local data!"

There are no functions, and thus no local data! The only data is a global variable. So what would this call stack look like? By default we call the portion where globals are defined the main function, or the main thread. For the purposes of the call stack alone, main can be treated as a function.

That’s it! That’s the basic call stack when you have nothing but globals and no functions. So let’s complicate this a little more. Let’s go back to our my_length function. Here is our new code:

def my_length(some_list, num):
    return num if some_list == [] else my_length(some_list[1:], num+1)

stuff = [0, 1]

my_length(stuff, 0)

So who do we do this? Well, we as we did before with the same main stack frame.

Now, however, main calls another function: my_length. And since every function gets its own frame on the stack, we need to add one to the stack. Stacks, however, are very special data structures. When we say add something to the stack, we use the term push onto a stack. So we push another frame onto the stack. It now looks like this.

There’s suddenly a lot more going on here! Let’s break it down. Stack frames grow downwards. So the top of the stack is the beginning. So first, main calls the function my_length, which is of course recursive.

At the very top is the name – my_length – nothing groundbreaking so far. The first call to my_length has the parameters stuff and 0, where the reference to the list is copied into some_list and 0 is copied into num. Great. Then there is the Return To. That’s not hard – main called us, so that’s where we’ll return.

But what does my_length return? Well, some_list is not [ ], which means that this isn’t a base case! So we have no idea what we’re returning. In fact, we have to finish the recursive call and use its return value. So let’s do that!

Like before, we’ve set up another stack frame, as every function call gets its own stack frame – even recursive ones.

So we see an arrow pointing to the return value of the next recursive call. The next one is a call to my_length once more. Here, however, some_list now just contains a single element, and num is equal to 1. Still, we’re not at the base case! So we must recurse once more. What do we return? Same as last time – since we don’t know, we must return the value of the recursive call.

So create another stack frame. This time we have reached the base case because some_list is an empty list! So we don’t have to recurse anymore – we know what we’re going to return: num. In this case, 2. And we have our full call stack! Now, since we’re at the base case, we can return a value!

What happens here is very important. Once a function hits either a return statment or the end of a function, several things happen:

Again, stacks are a special data structure. Removing something from a stack is called popping off the stack. By popping the frame off the stack, any local variables in that function call are gone forever. So our new stack now looks like this.

Now, my_length(1) has its return value of 2, and it, too, is ready to return! So it does the same three things:

Illustrated once more, that looks like this.

Now, the first recursive call also has the information it needs.

Finally, after all this work, my_length knows its return value! So it returns 2 to main, which then prints that value to the console, and the stack frame allocated for my_length is then popped off the stack as well, giving us the same stack we saw before with just one frame for main.

Limits To Recursion

So now you know what stack frames are and how they work. Remember that tidbit about how functions don’t get to access other functions’ stack frames? Thats why we can’t do this:

def hi():
    a = 5

def dude():
    print a

The stack is one way in which Python enforces the scope of variables.

So any guesses as to why the code at the beginning would cause a RuntimeError? Here’s a hint: stack frames consume memory! They’re not free. We have to store all those variables and return values somewhere. It costs memory.

In the case of the my_length function, 1000 recursive calls caused way too big of a stack, which is why Python complained. Essentially, it was saying the stack got too big, and it ran out of memory. So it crashed.

So even though this wasn’t infinite recursion, it was still too much recursion. Recursion has its limits, so there are certainly times in which the iterative approach is better.

In reality, is this a huge problem? Not in this class. The problems we give you won’t necessitate thousands of recursive calls, so don’t worry about it. Just know that recursion does come at a price (more memory in the stack), and that there are limits to this!