Recursion

The Call Stack

Lesson

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

But how does the computer actually run this code? It turns out that when the computer calls any function, it adds it to a data structure called the "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.

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).

Call Stack Memory = O(number of calls * memory per call)\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)O(n)

Mark as Completed:
Submits:
test
Test your code to get an output here!