Recursion

The Call Stack

Lesson

We've been writing lots of recursions like this one:

# copied from the Tree Height problem
def height(node):
    if node == None:
        return 0
    heightL = height(node.left)
    heightR = height(node.right)
    return max(heightL, heightR) + 1

But how does the computer actually run this code?

There is a single important idea to understand about all code: computers read it in order like a book. They go line by line running code, and if they see a function being called, they go run that line by line. It turns out that the storage system they naturally want to use to do this, in every underlying programming language, is a Stack. Specifically, it is referred to as the "call stack".

When the computer calls any function, it stores it in its internal "call stack". And when it finishes, the computer removes it from the Call Stack:

The computer always runs the top function in the Call Stack.

Example

Here's an example. The process is pretty long, but the computer is just following the simple process we described above.

Open SpoilerClose Spoiler

Say we call our height function on the tree below.

The very first thing that happens when we call height(A) is that the computer adds it to the Call Stack.

The computer then sees that height(A) is at the top of the Call Stack, so it starts computing height(A). Eventually, the computer gets to line 4, and has to make another function call height(B).

The computer adds height(B) it to the Call Stack. It saves information on how to resume $\small \texttt{ height(A)}$ when $\small \texttt{ height(B)}$ finishes:

Now height(B) is on top of the Call Stack, so the computer starts running it. It eventually reaches another function call height(None):

So it and adds it to the Call Stack:

Now the function call height(None) is on top of the Call Stack, so the computer runs it. It gets to the base case, and returns 0.

Now height(None) finished, so the computer removes it from the Call Stack. It updates the variables inside of the height(B) function accordingly.

The Call Stack now has height(B) on top, so it resumes this function where it left off. Now it knows that heightL = 0. So the computer resumes at line 5:

We won't go through the steps, but the same exact thing happens again, and the computer finds that heightR = 0. The computer then returns max(0, 0) + 1, which is 1.

Since the computer finished height(B), it removes it from the Call Stack. It updates the variables in height(A) accordingly.

It now resumes height(A) on line 4, and knows that heightL = 1.

Similar to above, the computer finds that heightR = 0. The computer then returns the last line max(1, 0) + 1, which evaluates to 2.

It then removes height(A) from the Call Stack, since it finished.

So the computer returns height(A), which is 2, as expected.

The main point: The Call Stack always grows to the maximum depth of your recursion.

For example, say we do a recursion on this tree.

The Call Stack is largest when the recursion reaches the deepest node in the tree (node C):

Space Complexity

Every recursive function uses extra memory, because the computer has to keep track of all the recursive calls it makes, using the Call Stack. To find the amount of memory a Recursion uses, you need to account for the number of calls in the Call Stack, and the memory used in each call (the memory used in each call is usually O(1) unless you store large data structures in your function calls).

\notag \text{Call Stack Memory = O(number of calls * memory per call)}

In our above example with the height function, the Call Stack grows to a height of O(n) calls, and each call stores a few of numbers, which is just O(1) memory per call. Multiplying these terms gives a total of O(n) * O(1) = O(n) total Space Complexity.

Space Complexity $O(n)$

Mark as Completed:

Submits:

test

Test your code to get an output here!