Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem, repeating until it reaches a defined stopping condition. It is a fundamental concept in computer science used to elegantly express solutions that have a naturally self-similar or hierarchical structure.
Recursion occurs when a function invokes itself as part of its own execution. Each call works on a smaller or simpler version of the original problem. This continues until the function reaches a base case — a condition that returns a result directly without making another recursive call. A classic example is computing a factorial: factorial(5) calls factorial(4), which calls factorial(3), and so on down to factorial(0), which returns 1.
Recursion allows complex problems to be expressed in clean, concise code that mirrors the problem's natural structure. Problems like tree traversal, graph search, divide-and-conquer algorithms, and parsing nested data are much easier to reason about recursively than iteratively. Many foundational algorithms — including merge sort, quicksort, and depth-first search — are defined recursively. Understanding recursion is essential for mastering data structures and algorithm design.
Every time a function is called, the runtime pushes a new stack frame onto the call stack, storing local variables and the return address. In a recursive function, each self-call adds another frame on top. When a base case is reached, the stack unwinds — each frame returns its result to the caller below it. Visualizing this stack behavior is key to understanding both the power and the limits of recursion.
Every correct recursive function must have two distinct parts: a base case and a recursive case. The base case defines when the function stops calling itself and returns a concrete value — without it, the function recurses infinitely. The recursive case breaks the problem into a smaller subproblem and passes it back to the same function. Ensuring the recursive case always moves toward the base case is the essential correctness requirement.
Because each recursive call consumes a stack frame, deeply nested recursion can exhaust the call stack and cause a stack overflow error. Languages like JavaScript, Python, and Java have a fixed default stack depth (often 1,000–10,000 frames). For problems with very large input sizes, an iterative approach or tail-call optimization (supported in some languages) may be necessary. Always analyze the maximum recursion depth your input could produce before choosing recursion.
A proven mental model is to trust that your recursive call correctly solves the smaller subproblem — focus only on handling the current step and delegating the rest. Write the base case first, verify it is correct, then define how the current call reduces the problem and combines results. Test with small inputs first, tracing the call stack manually to confirm correctness before scaling up. This disciplined approach prevents the common mistake of over-complicating recursive logic.
© RM Full Stack & AI Engineer · All guides · Roadmaps · Open the app