Recursion
The Call Stack
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.
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 height(A) when 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).
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)