Recursion

Some problems are naturally described in terms of smaller versions of themselves. The factorial of 4 is 4 times the factorial of 3. A directory's total size is its files plus the total sizes of its subdirectories. A syntax tree's node count is 1 plus the counts of its children. Recursion is the programming move that takes such definitions literally: write a function that, to solve the big problem, calls itself on the smaller one. It looks circular. It is not, provided two rules hold, and everything in this lesson flows from them.

• The base case: an input small enough to answer directly, with no further calls. For factorial, the factorial of 1 is just 1.
• The recursive case: solve a strictly smaller version of the problem, then combine its answer into yours. Factorial of n is n times factorial of n minus 1.

The classic picture is a line of people in a dark theater. You want to know your row number, so you ask the person in front: what row are you in? They do not know either, so they ask the person in front of them, and so on, until the question reaches the front row, where someone can simply see they are in row 1. That is the base case. Now the answers flow backward: row 1, so row 2, so row 3, each person adding one, until the answer arrives back at you. Every recursive function is this theater: questions pass forward until one is trivially answerable, then answers fold back.

Break either rule and the theater goes wrong. With no base case, or with calls that fail to shrink the problem, the questions never stop: each call spawns another forever. Real machines stop it for you, rudely, with the error every programmer eventually meets: stack overflow. Understanding why it is called that requires meeting the machinery that makes recursion possible at all.

The call stack: where the pending work lives

When any function is called, the runtime pushes a frame onto the call stack: a small block of memory holding the function's parameters, its local variables, and the return address, meaning where to resume when this call finishes. When the function returns, its frame is popped and the caller's frame is on top again. You met this structure in the memory lesson of Level 0; recursion is where it stops being background machinery and becomes the star. A function that calls itself simply stacks several frames of itself, each with its own copy of the parameters, and none of them collide because each lives in its own frame.

This is also the honest accounting for recursion's hidden cost. If the calls go n deep before hitting the base case, then n frames are alive at the deepest moment, which is O(n) space even if no visible variable grows. The previous lesson promised an example of memory that is easy to miss; this is it. And a recursion that never reaches its base case pushes frames until the stack's memory region is exhausted, which is exactly the overflow the error message names.

Tracing factorial of 4, both directions

factorial(4)                      the winding down
  4 * factorial(3)
        3 * factorial(2)
              2 * factorial(1)
                    1             base case: answers directly

              2 * 1 = 2           the unwinding
        3 * 2 = 6
  4 * 6 = 24

Read the trace top to bottom, then bottom to top. Four frames stack up, factorial of 4, 3, 2, 1, and each of the first three is paused mid-multiplication, waiting on the call below it. The base case answers without asking anyone. Then the stack unwinds: each pop completes one waiting multiplication. Four calls deep means O(n) time and O(n) space for factorial of n. The playground below makes both phases explicit. One honest note: the teaching language deliberately has no function calls, its grammar is too small to escape from, so the two phases of the recursion are simulated with loops. The winding loop plays the role of pushing frames, the unwinding loop plays the role of popping them, and the numbers match the trace above exactly.

When recursion explodes: Fibonacci

Factorial makes one recursive call per level, a straight line of frames. Now consider the Fibonacci numbers, where each number is the sum of the previous two. The direct recursive translation calls itself twice: fib(n) computes fib(n-1) plus fib(n-2). Two calls each spawn two calls, which spawn two more, and the call tree doubles in width every level. Drawing it for fib(5) is sobering: 15 calls, and fib(2) alone is computed three separate times from scratch. The recursion recomputes identical subproblems exponentially often, and the running time is O(2^n), the bottom rung of the complexity ladder. At n = 50, a naive recursive Fibonacci performs on the order of a trillion calls to determine one number.

fib(5)
|- fib(4)
|  |- fib(3)
|  |  |- fib(2)   <- computed here
|  |  |- fib(1)
|  |- fib(2)      <- and again here
|- fib(3)
   |- fib(2)      <- and again here
   |- fib(1)

15 calls for fib(5). the tree doubles each level: O(2^n).

The repair is one idea with a fancy name: remember answers. Store each fib(k) the first time you compute it, and return the stored copy on every later request. This is memoization, and it collapses the exponential tree to a straight line, each subproblem computed once, O(n) time, at the price of O(n) storage for the remembered answers. It is the canonical opening example of dynamic programming in MIT's 6.006, and it is the purest demonstration of the time-for-space trade from the previous lesson. The iterative version below is the same insight taken to its limit: keep only the last two answers, since that is all the recurrence ever reads, and the space cost falls to O(1).

Recursion in shipped and protected code

Recursion is load-bearing across this Academy. The parsers of Level 3 are recursive by construction, a recursive-descent parser is a family of functions that call each other in the exact shape of the grammar, and every tool that walks a syntax tree, including obfuscators and deobfuscators, recurses over child nodes. On the analysis side, the call stack is a favorite observation point: the debugger lesson showed that a paused program's stack is a readable history of how execution got there, and deep or oddly shaped stacks are one of the signals attackers read. Some protections exploit the machinery in the other direction, hiding control flow in convoluted call chains precisely because stack depth is finite and analysis tools must model it.

Recursion works when every call either answers a base case directly or makes strict progress toward one. The call stack holds one frame per pending call, so depth is space: O(depth) memory, and infinite depth is a stack overflow. When a recursion recomputes the same subproblems, remembering answers can collapse exponential time to linear, the flagship victory of complexity thinking.

Frequently asked questions