RecursionLesson 2

The Call Stack

What happens in memory when a function calls itself — stack frames, winding up, unwinding, and stack overflow.

What Is It?

Every time a function is called, the computer needs to remember where to come back when that function is done. These "reminders" stack up. That is the call stack.

More specifically: when you call a function, the computer creates a stack frame and pushes it onto the call stack. This frame stores:

  1. The arguments you passed in.
  2. Any local variables declared inside the function.
  3. Where to go back when this function returns.

When the function finishes, its frame is popped off the stack and execution continues from where it left off.

For recursion, this is what makes it work. Each recursive call gets its own frame with its own copy of the variables. The frames pile up during the winding phase and come off during the unwinding phase.

Analogy

Imagine a stack of sticky notes on your desk. Each note is a task you were in the middle of when a subtask came up.

You are working on Task A. It needs Task B done first. You write "Task A — paused, remember value 10" on a note, put it on the stack, and start Task B. Task B needs Task C. You write "Task B — paused, remember value 5" and stack it. Task C is simple — you finish it (base case!). You peel off the top note (Task B), resume from where you left off using the saved value. You finish Task B, peel off the next note (Task A), resume, and finish.

Each sticky note is a stack frame. Too many nested tasks and your desk overflows — that is a stack overflow.

How It Works

The Call Stack for factorial(4)

pseudocode
1
2
3
4
function factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
Call Stack: factorial(4)— Watch the stack grow during winding, then shrink during unwinding
1 / 10
Call factorial(4)
factorial(4) n=4
[0]

Final answer: 24.

Stack Overflow

The call stack has a limited size. If recursion goes too deep, you run out of space and the program crashes with a stack overflow error.

This happens in two ways:

Missing base case (infinite recursion):

pseudocode
1
2
function oops(n):
    return oops(n + 1)    // no base case — calls forever

Input too large even with a correct base case:

pseudocode
1
factorial(100000)    // 100,000 frames deep — likely crashes

This is why iterative solutions are sometimes preferred for very large inputs.

Each Frame Has Its Own Variables

This is important to understand. When factorial(4) calls factorial(3), the n=4 in factorial(4) does NOT get overwritten by n=3. Each frame has its own separate copy of n.

pseudocode
1
2
3
4
5
  factorial(4): n = 4  <-- n=4 lives here, separate from all others
  factorial(3): n = 3  <-- n=3 lives here
  factorial(2): n = 2  <-- n=2 lives here
  factorial(1): n = 1  <-- n=1 lives here
  factorial(0): n = 0  <-- base case

Stack Depth of Common Recursive Functions

factorial(n)
0O(n)
fibonacci(n)
0O(n)
binarySearch(arr)
0O(log n)
DFS on graph
0O(V)

The Two Phases

Winding

  • factorial(4) calls factorial(3)
  • factorial(3) calls factorial(2)
  • factorial(2) calls factorial(1)
  • factorial(1) calls factorial(0)
  • factorial(0) — base case reached

Calls go deeper, stack grows

each call waits for the next

Unwinding

  • factorial(0) returns 1
  • factorial(1) returns 1 * 1 = 1
  • factorial(2) returns 2 * 1 = 2
  • factorial(3) returns 3 * 2 = 6
  • factorial(4) returns 4 * 6 = 24

Returns propagate back, stack shrinks

return values flow upward

Examples

The Call Stack for Non-Recursive Code

Even regular (non-recursive) functions use the call stack:

pseudocode
1
2
3
4
5
6
7
function main():
    x = add(3, 4)
    print(x)
​
function add(a, b):
    result = a + b
    return result

While add is running, the stack looks like this:

pseudocode
1
2
3
4
5
6
7
8
+------------------+
| add(3, 4)        |  <- top frame
|   a=3, b=4       |
|   result=7       |
+------------------+
| main()           |
|   x=(waiting)    |
+------------------+

add returns 7, its frame is popped, and main gets the value 7.

The Call Stack for Fibonacci

pseudocode
1
2
3
function fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

For fib(4), the stack goes down the left branch first:

pseudocode
1
fib(4) -> fib(3) -> fib(2) -> fib(1)  <- deepest point

Maximum stack depth is 4 (not the total number of calls). The stack only holds the current path being explored — not all paths at once.

Common Mistakes

  1. Thinking each frame stores a copy of the entire array. Only the function's arguments and local variables are stored. If you pass an index into an array, the frame just stores that small index — not the whole array.
  1. Confusing the call tree with the call stack. The call tree shows every call ever made. The call stack shows only the calls currently running. The stack is always one single path through the call tree.
  1. Underestimating stack overflow risk. Recursive DFS on a graph with 100,000 nodes in a chain can crash. Always think about the maximum recursion depth.
  1. Forgetting that stack space counts as memory usage. A recursive function with depth n uses O(n) memory even if it does not create any arrays or data structures.

Best Practices

  • Always think about the maximum recursion depth when analyzing space complexity.
  • Switch to an iterative approach when the depth could exceed a few thousand levels.
  • Draw the stack frames when debugging. Seeing each frame's variables makes it immediately clear what is happening at each level.
  • Remember: the stack only holds the current path, not all calls ever made. For fibonacci(n), the stack depth is n even though the total calls is 2^n.
Understanding RecursionWriting Recursive Functions