vizlearn
Home / Algorithms

Recursion and the Call Stack

Algorithms & Data StructuresBy Updated

A function that calls itself is not magic — it is stack frames piling up and unwinding. Watch them build, watch the answers come back, and watch naive Fibonacci explode into thousands of redundant calls.

Controls

n5

The Call Stack

step 0
Stack frames (newest on top)
Call trace

Insight

Every call pushes a stack frame holding its arguments, locals and return address. Returning pops it. Recursion is just this, repeated.

total calls0
max depth0
result–

Complexity

factorial O(n)
fib naive O(2^n)
fib memoised O(n)

Overview

Recursion solves a problem by calling the same function on a smaller instance. A base case stops; each recursive call must make progress toward it. For factorial, each call reduces n until it reaches 1:

The two required parts

def factorial(n):
    if n <= 1:                 # base case
        return 1
    return n * factorial(n-1)  # smaller problem

If the recursive case does not make progress, the function may run until the language’s recursion limit or stack capacity is reached.

What the call stack remembers

When factorial(5) calls factorial(4), the first call pauses with its value of n and waits for the result. Each call has its own frame. Once the base case returns, frames resume in reverse order: 1 × 2 × 3 × 4 × 5 = 120. The visualizer shows those frames building on the way down and unwinding on the way back.

Choose countdown — no base case to see frames accumulate without returning. Then compare fibonacci — naive with memoised at the same input. The naive version recomputes overlapping subproblems and takes exponential time; memoization stores each result so it is computed once. This is a useful bridge to dynamic programming.

When recursion fits

Recursion often matches tree traversal, nested data, divide-and-conquer, and backtracking because each naturally contains smaller instances of the same problem. A loop is usually simpler for a flat sequence. Deep recursion can also use more stack space than an iterative solution; Python does not optimize tail calls into loops.

Common mistakes with Recursion and the Call Stack

  • Missing or unreachable base case: calls never return.
  • Not shrinking the problem: the recursive case repeats the same state.
  • Forgetting to return the recursive result: the caller receives None in Python.
  • Recomputing repeated subproblems: add memoization when the recurrence revisits states.
  • Using recursion for very deep input: consider an explicit stack or loop.

Sources and next steps

Run it in Python

Factorial with its frames printed as they are pushed and popped, then the same problem written as a loop, then the recursion limit hit on purpose — because a stack overflow is much easier to understand once you have caused one.

recursion.pyPython 3
Output
How the code works
  1. if n <= 1: return 1The base case, and the only thing standing between this function and a crash. Every recursive function needs one, and every call must make measurable progress towards it.
  2. result = n * factorial(n - 1, depth + 1)The multiplication happens after the recursive call returns, so the frame has to stay alive while the whole subtree below it runs. That is precisely what the call stack is holding.
  3. the indented print pairsEach call line has a matching return at the same indent. Read downwards for the pushes and upwards for the pops — the output is the stack, drawn over time.
  4. except RecursionError: return 0Python caps the depth deliberately, because the real C stack underneath would otherwise be overrun and the process would die rather than raise. The limit is a guard rail, not the actual capacity.
  5. calls += 1 in fibNaive fib recomputes the same subproblems exponentially often. Recursion is not slow; recursion without memory is.
Change one thing
  • Delete the base case from factorial. The RecursionError traceback is what an infinite recursion looks like from the inside.
  • Call fib(30) and then fib(32). Roughly four times the calls for two more terms — and it is about to get much worse.
  • Rewrite factorial so the recursive call is the last thing it does (pass the accumulator down). That is tail recursion — and CPython still will not optimise it away.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set n to its maximum (12). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. What does a stack frame hold?
  2. In 'return n * factorial(n - 1)', why can the frame not be discarded at the recursive call?
  3. The program prints call counts for naive fib. What is the shape?





 Cheat sheet
Recursion and the Call Stack
Watch each recursive call push a frame onto the call stack, and see the values computed on the way back up, not the way down.
ALGORITHMS · vizlearn.in/dsa/recursion_and_call_stack.html
More in Algorithms
AlgorithmsDivide and ConquerAlgorithmsMerge SortAlgorithmsQuick SortAlgorithmsCounting Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact