Pointer Walk

The Call Stack

Recursion is a tall stack: each call adds a frame, then the tower pays back from the top. Remove the base case and it overflows.

Languages and RuntimesBeginner8 min read

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.

  1. A call pushes a new frame on top

    The function that is running is always the top frame.

  2. A return pops the top frame off

    Its variables are gone, and the frame below carries on.

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

python
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)
factorial(4) and the call stackInteractive
1def factorial(n):
2 if n == 1:
3 return 1
4 return n * factorial(n - 1)
5
6print(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.

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

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress