# 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)
10
``````

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
• stack

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.

• function name
• one slot per parameter (parameters first!)
• one slot per local variable
• return value
• to what does the function return (to main? to another function? etc)

So let’s look at the file `boring.py`.

``````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:

• The function returns the value computer to whoever called it
• It deletes everything local to that stack frame
• It pops that frame off the stack (deletes that frame off the stack)

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:

• Returns `2` to `my_length`, which is the function that called it
• Deletes everything local to that stack frame
• Pops that stack frame off the stack

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!