Recursion visualizer

Choose a function, type its input, and press Step to make one call or return at a time, or Play to run it. Each box in the tree is one call; it is highlighted while it is on the call stack, and shows its return value once it finishes. The panel on the right lists the stack from the running call down to the first one, each waiting for the call above it.

• For Fibonacci and binomial coefficients, turn on Memoization to see repeated calls answered from a table instead of recomputed.
• Copy answer gives the whole call trace, indented by depth, the way exercises ask for it; Copy link saves the function, input and step.

A function is recursive when it calls itself. It works when two things are true: there is a base case, an input small enough to answer directly, and every other input is handled by a recursive case that calls the function on something closer to the base case and combines the result.

Factorial is the standard first example: 0! is 1, and n! is n × (n − 1)!. Computing fact(5) calls fact(4), which calls fact(3), and so on down to fact(0), which returns 1. The calls then finish in reverse order, each multiplying by its own n, until fact(5) returns 120. That is 6 calls in all.

Each call needs its own copy of its arguments and local variables, and must remember where to continue when it finishes. The program keeps these in a stack frame, and the frames of all calls in progress form the call stack. A call pushes a frame; a return pops it. The stack therefore holds exactly the calls that have started and not yet returned, with the running call on top and every call below it waiting for the one above.

The deepest the stack gets is the recursion's depth, and it decides how much memory the recursion needs. fact(5) reaches 6 frames. Plain Fibonacci makes far more calls but only goes as deep as its longest chain, n frames for fib(n): fib(30) makes 2,692,537 calls but never has more than 30 frames on the stack at once. A recursion that is too deep exhausts the space reserved for the stack, which is a stack overflow.

Drawing each call as a node, with an edge to every call it makes, gives the recursion tree. Factorial's tree is a single chain. Fibonacci's branches twice at every call that is not a base case, because fib(n) needs both fib(n − 1) and fib(n − 2), so the number of calls grows exponentially: it is 2F(n + 1) − 1, where F(n) is the nth Fibonacci number.

Memoization stores each result in a table the first time it is computed. A later call with the same arguments looks the answer up and returns at once, without making any calls of its own. Fibonacci then computes each of fib(0) to fib(n) once, and the total falls to 2n − 1 calls, as the table above shows. Binomial coefficients behave the same way: computing C(20, 10) = 184,756 with the plain recursion takes 369,511 calls, and with memoization 201.

Python's standard library builds this in as functools.lru_cache, and its documentation uses Fibonacci as the example. A single memoized fib(15) in this visualizer computes 16 different values and answers 13 calls from the table. Memoization only helps when calls repeat: factorial and fast power never call themselves twice with the same arguments, so a table would never be used. Filling the same table from the bottom up, without recursion, is dynamic programming's other form, tabulation.

Recursion trees are also a tool for analysing divide-and-conquer algorithms. Merge sort splits an array in half, sorts each half recursively and merges them, so its running time satisfies T(n) = 2T(n/2) + n. Drawing the tree and adding up the work at each level solves it: every level merges all n elements between its calls, and halving reaches single elements after log₂ n levels, so the total is about n log₂ n.

The "Merge sort calls" function shows this exactly. For 16 elements, the levels merge 16, 16, 16, 16 elements, 4 levels of 16 and 64 in total, from 31 calls. For 1,000 elements, which do not halve evenly, there are 10 levels and 9,976 elements merged.

The puzzle moves a stack of n disks from peg A to peg C, one disk at a time, never placing a larger disk on a smaller one. The recursive solution moves the top n − 1 disks to the spare peg B, moves the largest disk to C, then moves the n − 1 disks from B onto it. The number of moves M(n) = 2M(n − 1) + 1 with M(1) = 1, which is 2ⁿ − 1. Three disks take these 7 moves:

1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

The count doubles with every disk: 3 disks need 7, 10 disks need 1,023, 20 disks need 1,048,575.

A call is a tail call when it is the last thing a function does, with nothing left to compute after it returns. Euclid's algorithm is tail recursive: gcd(a, b) simply returns gcd(b, a mod b). Factorial as written above is not, because each call still has to multiply by n after the inner call returns. gcd(252, 105) goes gcd(252, 105) → gcd(105, 42) → gcd(42, 21) → gcd(21, 0), returning 21.

Because nothing is waiting in a tail-calling frame, a language can reuse the frame instead of pushing a new one, so tail recursion runs in constant stack space, like a loop. The Scheme standard requires implementations to be properly tail recursive in this sense. Many other languages make no such promise, so a deep tail-recursive function can still overflow the stack there, and is better written as a loop.