A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A recursive function is one that calls itself as part of its own definition. Every recursive solution requires a base case (a condition that terminates the recursion) and a recursive case (a call on a smaller or simpler version of the problem). Each function call creates a new stack frame with its own local variables; the call stack grows with each recursive call and shrinks as calls return. Many problems — especially those with naturally recursive structure like trees or mathematical sequences — are elegantly expressed recursively.
Start with factorial and Fibonacci, tracing the call tree by hand. Then implement recursive sum of a list, string reversal, and binary search. Always identify the base case first before writing the recursive case.
You already know that functions can call other functions — that is how you have been building programs. Recursion takes this one step further: a function can call *itself*. At first this seems paradoxical, but it is one of the most powerful ideas in programming.
The key insight is that many problems have a self-similar structure. The factorial of 5 (written 5!) equals 5 × 4!. And 4! = 4 × 3!. And so on. Once you see this, a recursive definition writes itself: `factorial(n) = n * factorial(n-1)`. But this chain has to stop somewhere — that is the base case. For factorial, `factorial(0) = 1` by definition. Without the base case, the chain never terminates and you get infinite recursion. Writing the base case *first*, before the recursive case, is the discipline that keeps you out of trouble.
When a recursive function runs, the call stack is doing the real work. Each call to `factorial(n)` creates a new stack frame — a small block of memory holding n and the return address. When `factorial(5)` calls `factorial(4)`, the first frame pauses and waits; when `factorial(4)` calls `factorial(3)`, another frame is added. The stack grows to depth n, then unwinds as each call returns its result up to the caller. This is why variable scope matters: each frame has its own copy of `n`, and there is no confusion between them. It is also why deep recursion can be expensive — you are allocating a frame for every level.
A common bug is calling the recursive function but not returning its result: writing `factorial(n-1)` instead of `return factorial(n-1) * n`. The deeper call runs correctly and computes the right answer, but that answer is thrown away because you never returned it. Always check that your recursive case both calls the function *and* uses the return value.
Recursion is not always the right tool. Simple loops — adding up a list, iterating over a string — are almost always clearer and more memory-efficient as iteration. Where recursion shines is on problems with naturally recursive structure: tree traversals, divide-and-conquer algorithms, parsing nested expressions. If you find yourself writing a loop and keeping an explicit stack to track state, that is a signal that recursion might be the cleaner solution. Over time, you will develop judgment about which to reach for.