Here's a definition that shouldn't work: to compute the factorial of 5, compute the factorial of 4 and multiply by 5. We just defined factorial using factorial, the way a dictionary might define a word with the word itself. So why doesn't the computation chase its own tail forever?

It never gets the chance, because each call shrinks the problem. Recursion is a technique where a function calls itself to break a complex problem down into simpler subproblems, and every call steps toward a problem so small it can be answered outright, the base case. Think of a set of nested dolls: each doll contains a smaller version of itself until you reach the smallest one. The doll picture leaves out half the work, though. After reaching the smallest doll, recursion has to close every doll back up in reverse order, combining answers on the way out.

Recursion has two essential pieces: the base case and the recursive case. The base case is what stops the recursion (without it, you get an infinite loop). The recursive case is where the function calls itself with a modified argument, gradually moving toward the base case.

This technique shows up in tree traversals, the Fibonacci sequence, and divide-and-conquer algorithms in general, where each recursive call peels off a smaller piece of the original problem.

Each recursive call creates a new execution context on the call stack, the same LIFO structure you met in the stacks section of the arrays page. The function does some work, then calls itself with a new argument that represents a smaller piece of the original problem. When the base case is finally reached, the function stops calling itself and starts returning values, unwinding the call stack in reverse order.

Watch factorial(4) actually run. The first call can't finish 4 × factorial(3) until factorial(3) reports back, so it waits on the stack while factorial(3) calls factorial(2), which calls factorial(1), the base case. Before reading the unwind, commit to a guess: at the deepest moment, how many calls are sitting on the stack at once? The answer is 4, every one of them frozen mid-multiplication. Then the dominoes fall in reverse: factorial(1) returns 1, which unfreezes 2 × 1 = 2, then 3 × 2 = 6, then 4 × 6 = 24. The descent asks the questions, and the unwind computes the answers.

You might think recursion is inherently slow, something to replace with loops whenever performance matters. The real costs are more specific. Every call holds a stack frame, so memory grows with the depth of the recursion, and deep recursion can overflow the stack. The other trap is repeated work: a naive recursive Fibonacci recomputes fib(20) exactly 1,346,269 times while evaluating fib(50). Memoization erases the repeated work, and converting to an iterative loop frees the stack when depth becomes the problem.

Recursion fits naturally on problems with a hierarchical structure, like tree and graph traversals, and on backtracking algorithms. Spotting when a problem can be broken into similar subproblems is most of the battle. As you solve more recursive problems, you'll start to see patterns that help you decide between a recursive and an iterative approach.

Recursion is one of the patterns that rewards careful planning: the base case, the recursive case, the stack budget, and any memoization. Here are a few habits that keep all four under control:

Before you start, quiz yourself on two things from this page: what are the two pieces every recursive function must have, and why does memoizing a recursive Fibonacci collapse its running time so dramatically? If both answers come back quickly, you're ready. Recursion clicks once you stop tracing the call stack and start trusting the recursive contract: "this function returns X for any subproblem." Work through these to internalize divide-and-conquer, recursive matching with memoization, and the recursive structure that underlies linked-list and tree problems: