Where does a function go when it calls another?
When function A calls function B, A has to stop and wait. When B finishes, A must carry on from exactly where it left off, with all its variables as they were.
Something has to remember "A was on line 12, and its total was 40". That something is the call stack.
A stack of frames
Each time a function is called, the computer creates a frame: a small block of memory holding
- the function's arguments and local variables, and
- where to continue in the caller when this function returns.
Frames are kept in a stack, like a stack of plates.
A call pushes a new frame on top
The function that is running is always the top frame.
A return pops the top frame off
Its variables are gone, and the frame below carries on.
Only the top frame is ever active
Everything below it is paused, waiting.
Last in, first out: the most recent call is always the first to finish.
Recursion is a tall stack
A function that calls itself is nothing special to the stack. Each call simply gets its own frame, with its own copy of the variables. That is how n can be 4 in one call and 1 in another at the same time.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)1def factorial(n):2 if n == 1:3 return 14 return n * factorial(n - 1)56print(factorial(4))
Variables
nothing yet
Start. Each call gets its own box on the stack, holding its own n. The top box is the one running.
Watch the shape. The tower grows as each call waits for the next one, reaches its full height at the base case, and then pays back from the top: each frame returns its answer to the frame beneath it and disappears.
Example
Reading the tower
At its tallest, the stack holds: factorial(4) waiting to multiply by 4, factorial(3) waiting to multiply by 3, factorial(2) waiting to multiply by 2, and factorial(1) about to return 1.
The multiplications have not happened yet. They happen on the way back down: 2 × 1, then 3 × 2, then 4 × 6.
Take away the base case
The base case, if n == 1, is what stops the tower growing. Remove it, or call factorial(0) so it is never reached, and each call makes another call for ever.
The stack is a fixed, fairly small region of memory. It fills up, and the program is stopped with an error:
- Python:
RecursionError: maximum recursion depth exceeded - Java:
StackOverflowError - JavaScript:
RangeError: Maximum call stack size exceeded
This is a stack overflow.
Reading a stack trace
When a program crashes, the error message lists the frames that were on the stack at that moment. That is a stack trace. It is a snapshot of exactly the tower in the animation.
Traceback (most recent call last):
File "shop.py", line 30, in <module>
checkout(cart)
File "shop.py", line 22, in checkout
total = price_of(item)
File "shop.py", line 9, in price_of
return prices[item.name]
KeyError: 'umbrella'Read it as a chain: the program called checkout, which called price_of, which failed on line 9. In Python the failure is at the bottom. Some languages print it the other way up.
Key takeaways
- The call stack remembers every function that is waiting for another to finish.
- Each call pushes a frame with its own variables. Each return pops one.
- Recursive calls stack up until the base case, then return one by one from the top.
- With no base case, or too much depth, the stack runs out of room: a stack overflow.
- A stack trace is a printout of the stack at the moment of an error.