What is Recursion

Recursion is a technique where a function solves a problem by calling itself with a smaller or simpler version of the same problem. Every recursive function has two parts: a base case that stops the recursion, and a recursive case that breaks the problem down and calls itself.

How it works

Consider computing the factorial of n (n! = n * (n-1) * ... * 1):

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1  ← base case

The base case is factorial(1) = 1. Without it, the function would call itself forever.

Each recursive call pushes a frame onto the call stack. The stack holds local variables and return addresses. When the base case is reached, the calls unwind — each frame pops off and returns its result to the caller above it. This is why deep recursion can cause a stack overflow: too many frames exhaust the stack memory.

Recursion is the natural way to process structures that are themselves recursive. A tree node contains child nodes, each of which is also a tree. Traversing a tree means visiting a node and recursing on its children. A file system, a JSON document, and a mathematical expression are all recursive structures that map cleanly to recursive code.

Not every recursive function is efficient. Computing Fibonacci numbers naively — fib(n) = fib(n-1) + fib(n-2) — makes an exponential number of calls because the same subproblems are solved repeatedly. Memoization and dynamic programming fix this by caching results.

Any recursive algorithm can be converted to an iterative one using an explicit stack, but the recursive version is often clearer. DFS and divide and conquer algorithms are almost always written recursively because the code mirrors the problem structure.

Why it matters

Recursion is fundamental to algorithm design. Tree traversal, graph search, sorting (merge sort, quicksort), parsing, and backtracking all rely on it. Understanding how recursive calls map to the call stack — and when to add memoization — is essential for writing correct and efficient algorithms.

See How Recursion Works for detailed examples and the transition to dynamic programming.