ƒ(x) PatternsIntermediate interactive
Recursion & The Call Stack
Functions that call themselves, one frame at a time.
fibonacci_recursion
step 1 / 31
5
4
3
2
1
0
1
2
1
0
3
2
1
0
1
call stack
fib(5)
call fib(5)
on call stackreturnedpending
speed1×
How it works
Recursion solves a problem by reducing it to smaller versions of itself until a base case stops the descent. Each call stacks a frame; each return unwinds one. Understanding the call stack demystifies memoization, backtracking, and tree algorithms.
Mental models
- Every recursion needs a base case or it overflows the stack.
- Naive recursion recomputes subproblems — memoization fixes it.
Complexity
- Time
- variesby recurrence
- Space
- O(depth)call stack
Reach for it when
- Tree/graph traversal
- Divide & conquer
- Backtracking