Concepts & Theory

Recursion Explained

Recursion is a function calling itself to solve a smaller version of the same problem. It's the natural way to express many algorithms that would otherwise require complex bookkeeping.

Published April 26, 2026

A recursive function is one that calls itself. Every recursive function needs two things: a base case (the simplest version of the problem, solved directly without recursion) and a recursive case (the general case, which reduces the problem and makes a recursive call). Without a base case, the function calls itself forever until the program crashes with a stack overflow.

The classic example: factorial

The factorial of n (written n!) is n multiplied by every positive integer smaller than it. 5! = 5 × 4 × 3 × 2 × 1 = 120. The recursive definition: factorial(n) = n × factorial(n-1), with factorial(0) = 1 as the base case.

def factorial(n):
    if n == 0:       # base case
        return 1
    return n * factorial(n - 1)   # recursive case

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 * factorial(0)
# = 5 * 4 * 3 * 2 * 1 * 1
# = 120

The call stack

Each function call is added to the call stack — a region of memory that tracks what to return to when a function finishes. When factorial(5) calls factorial(4), the current frame (including the value of n=5) is saved on the stack. When factorial(0) returns 1, the stack unwinds: each frame multiplies by its n and returns, until we're back at the original call.

This is why deep recursion can cause a stack overflow: you're limited by the maximum stack depth (often around 1,000 frames in Python, configurable but still finite). For very deep recursion, use iteration or tail call optimization (if your language supports it).

When recursion is the right tool

Recursion shines when the problem has a naturally recursive structure:

Tree traversal: a tree is either empty or a node with children that are trees. Traversal is recursive by definition.
Divide-and-conquer algorithms: merge sort, quicksort, and binary search all split a problem in half recursively.
File system traversal: a directory contains files and other directories (which contain files and other directories...).
Parsing nested structures: JSON, HTML, and most programming language parsers use recursion to handle nesting.

# Tree traversal: natural fit for recursion
def sum_tree(node):
    if node is None:
        return 0
    return node.value + sum_tree(node.left) + sum_tree(node.right)

Fibonacci and the cost of naive recursion

The Fibonacci sequence (1, 1, 2, 3, 5, 8, 13...) is often used to teach recursion, but the naive implementation is a bad real-world example:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)   # calls itself TWICE

This has exponential time complexity, O(2^n), because it recomputes the same subproblems repeatedly. fib(50) would take minutes. The solution is memoization (caching results) or dynamic programming (computing bottom-up):

# With memoization (Python's functools.cache)
from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

fib(100)   # instant

Mutual recursion

Two functions can call each other recursively. A classic example is checking whether a number is even or odd without using modulo:

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

Mutual recursion can model state machines and parsers elegantly, though it requires care to ensure both functions always make progress toward a base case.

Recursion vs. iteration

Any recursive algorithm can be rewritten as an iterative one using an explicit stack (you're just managing the stack yourself rather than relying on the call stack). The iterative version uses constant stack space, which matters for large inputs. The recursive version is often easier to read and reason about for naturally recursive problems.

The practical rule: use recursion when the recursive structure is obvious and the depth is bounded and reasonable. Use iteration when you're working with very large inputs, when your language doesn't optimize tail calls, or when the iterative version is equally clear.