Recursion

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.

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

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

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: