Recursion
Understand recursion visually using factorial and Fibonacci
Visual by thisgirltech
Two classic recursion problems side by side. The Factorial tab shows a linear call stack: factorial(5) pushes 6 frames, hits the base case factorial(0) = 1, then unwinds — each frame multiplying its value before popping. The Countdown tab shows simple linear recursion with no return value.
Watch the call stack depth counter grow and collapse back to 0. The gap between a recursive and iterative solution — especially once you see Fibonacci — is exactly why memoisation and dynamic programming exist.
Every function call allocates a stack frame: space for local variables, the return address, and the arguments. Deep recursion fills this memory. Stack overflow errors happen when recursion is too deep — typically around 1,000–10,000 frames depending on the language.
Factorial is linear — each call makes exactly one recursive call. The stack grows and shrinks like a single column. Fibonacci is tree recursion — each call makes two recursive calls. This is why factorial is O(n) and naive fib is O(2ⁿ).
When the base case is hit, it returns a value. That value is passed back to the caller, which uses it to compute its own return value, and so on up the chain. The result flows back through every frame in reverse order of how they were pushed.
Every recursive algorithm can be rewritten iteratively — sometimes trivially (factorial), sometimes requiring an explicit stack (tree traversal). Recursion trades stack memory for code clarity.
Notice that each frame shows 'waiting' while deeper calls run. The multiplication only happens on the way back up — that is the unwinding phase. This is the key mental model for all linear recursion.
COLOUR LEGEND