Recursion – call stack and call tree

What it shows

A recursive function solves a problem by calling itself on a smaller version of the same problem. Each call pushes a new frame onto the call stack; the base case returns without calling again, and the frames then unwind as values are passed back up. The call tree shows every call: factorial and list sum make a single chain, while Fibonacci, merge sort and the tower puzzle branch. Naive Fibonacci repeats the same calls many times, so the number of calls grows exponentially; memoisation stores results so each value is computed once. Without a base case the recursion never stops and the stack overflows.

How to use

Choose a Function and set n (or the target for binary search). Press Step to make one call or return at a time, Back to undo a step, or Run to play at the chosen Speed. Watch the code, the call stack and the call tree; tap a node for details. Tick Memo for Fibonacci or untick Include base case to see a stack overflow. Compare with the loop version below.

Parameters you can change

• Recursive function Factorial n!, Fibonacci numbers, Sum of a list, Binary search, Tower puzzle (moving disks), Merge sort
• n (size of the problem) 0–8
• Value to find (binary search) 0–100
• Memoisation (Fibonacci)
• Include the base case
• Language Python, Pseudocode
• Run speed 0.5–10 steps/s

Questions to explore

1. How many times is fib(2) called when you compute fib(6) without memoisation, and how many times with it?
2. What is the maximum stack depth for factorial(5), and how much stack does the loop version need?
3. Why does removing the base case cause a stack overflow instead of a wrong answer?