Recursion

What is recursion?#

Recursion is when a function calls itself in order to solve a smaller version of the same problem. It can feel circular or even paradoxical the first time you see it — "how can a function be finished before it's finished?" — but it becomes very natural once you see the two-part structure every correct recursive function needs.

Analogy: imagine a set of Russian nesting dolls. To find out what's inside the whole thing, you open the outer doll, and inside is... a smaller doll, which you handle exactly the same way: open it, find another smaller doll inside. Eventually you reach the smallest doll — solid, nothing more to open — and that's your stopping point. Recursion is exactly this: solve a big problem by handling one small piece of it, then handing off an almost-identical, slightly-smaller problem to another copy of the same procedure, all the way down until the problem is trivially small.

Base case and recursive case#

Every correct recursive function needs exactly two parts:

• The base case — the smallest version of the problem, simple enough to answer directly, with no further recursive calls. This is what stops the recursion.
• The recursive case — the general version, which solves the problem by calling itself on a smaller piece of the same problem, then combining that result with something to produce the final answer.

Miss the base case (or write it so it's never actually reached), and the function calls itself forever — until it crashes with a stack-related error, which we'll come back to at the end of this page.

Factorial, traced step by step#

factorial(n) (written n!) is defined as n × (n-1) × (n-2) × ... × 1, with factorial(0) defined as 1. This definition is already recursive in spirit — n! is just n times (n-1)! — which makes it the classic first example.

def factorial(n):
    if n == 0:                      # base case: the smallest version of the problem
        return 1
    return n * factorial(n - 1)     # recursive case: solve a smaller version, then combine

print(factorial(4))   # 24

Let's trace exactly what happens when you call factorial(4), one call at a time:

factorial(4)
  = 4 * factorial(3)
      = 4 * (3 * factorial(2))
            = 4 * (3 * (2 * factorial(1)))
                  = 4 * (3 * (2 * (1 * factorial(0))))
                        = 4 * (3 * (2 * (1 * 1)))     <- base case hit: factorial(0) = 1
                        = 4 * (3 * (2 * 1))
                  = 4 * (3 * 2)
            = 4 * 6
      = 24

Notice the shape: the calls first go "downward," each one waiting on the next, until the base case finally gives back a real number instead of another call. Then the answers "unwind" back upward, each waiting call finally able to multiply and return.

The call stack, visualized#

That "waiting" is not a metaphor — it's a literal data structure. Every time a function calls another function (including calling itself), the calling function's state gets pushed onto the call stack — the exact same stack structure covered in the data structures course, applied here by the language runtime itself, automatically. When factorial(4) calls factorial(3), Python doesn't discard factorial(4)'s progress; it pauses factorial(4) (remembering that it still needs to multiply its result by 4 once it comes back) and pushes a new frame for factorial(3) on top.

Call stack while factorial(0) is executing (deepest point):

|  factorial(0)   |  <- top of stack — currently executing
|  factorial(1)   |     "waiting: return 1 * (whatever factorial(0) gives back)"
|  factorial(2)   |     "waiting: return 2 * (whatever factorial(1) gives back)"
|  factorial(3)   |     "waiting: return 3 * (whatever factorial(2) gives back)"
|  factorial(4)   |     "waiting: return 4 * (whatever factorial(3) gives back)"
------------------

Once factorial(0) returns 1, its frame is popped off the stack (LIFO — last in, first out, exactly like the stacks page described), and factorial(1) resumes exactly where it left off, now able to compute 1 * 1 and return 1 itself — which pops its frame, letting factorial(2) resume, and so on, all the way back to the original call. This is precisely why unbounded recursion causes a "stack overflow": every unfinished call sits on the stack taking up real memory, and if the base case is never reached, that stack keeps growing until it runs out of room.

A classic recursive problem: Fibonacci#

The Fibonacci sequence is defined recursively in the most direct way possible: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1.

def fib_naive(n):
    if n <= 1:                                   # base case
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)    # recursive case

print(fib_naive(6))   # 8

This is correct — and also a perfect illustration of recursion's biggest performance trap. Each call to fib_naive(n) makes two further recursive calls, and those calls overlap heavily: computing fib_naive(5) requires fib_naive(4) and fib_naive(3), but computing fib_naive(4) also requires computing fib_naive(3) all over again, from scratch, with no memory of having done so a moment ago.

                          fib(5)
                       /          \
                 fib(4)            fib(3)
                /      \           /      \
           fib(3)     fib(2)   fib(2)    fib(1)
           /    \      /   \    /   \
       fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
       /   \
   fib(1) fib(0)

Notice fib(3) gets computed twice, fib(2) gets computed three times, and so on — this redundant re-computation makes the naive version run in O(2ⁿ) time (exponential — it roughly doubles in work for every one step you increase n), which becomes unusably slow surprisingly quickly (fib_naive(40) already takes a noticeable pause; fib_naive(50) is effectively impractical).

Fixing it with memoization#

Memoization means caching the result of each unique call, so that if the same input is ever asked for again, you return the cached answer instantly instead of recomputing it:

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:                      # already computed this exact subproblem — reuse it
        return cache[n]

    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(fib_memo(50))   # 12586269025 — instant, where the naive version would be impractically slow

With memoization, each unique fib_memo(k) is computed exactly once and then reused every subsequent time it's needed, bringing the total time down from O(2ⁿ) to O(n) — a change to the code's strategy, not its hardware, that turns an impractical function into an instant one. (This exact idea — noticing overlapping subproblems and caching their results — is the entire foundation of the dynamic programming page later in this course.)

When recursion is elegant vs when it risks trouble#

Recursion genuinely shines when a problem's structure is naturally recursive — trees (a subtree is just a smaller tree), divide-and-conquer algorithms (a smaller version of the same problem, solved the same way), or anything defined recursively to begin with (like factorial or Fibonacci themselves). In these cases, the recursive solution is often dramatically shorter and easier to read than an equivalent loop-based version.

But recursion has two real costs to keep in mind:

• Stack depth. Python's default recursion limit is 1,000 calls deep (sys.getrecursionlimit()) — recursing on something proportional to a very large input (say, a plain loop-shaped recursive function over a million-element list) will hit a RecursionError well before an equivalent iterative loop would have any trouble at all.
• Repeated work, as Fibonacci demonstrated — a recursive solution with overlapping subproblems can be exponentially slower than necessary unless paired with memoization (or rewritten iteratively).

A reasonable rule of thumb: reach for recursion when the problem is naturally hierarchical/self-similar (trees, divide and conquer) and the recursion depth is bounded by something like log n (which stays small even for huge inputs) rather than n itself (which can blow the stack for large inputs). When recursion depth would scale linearly with a potentially huge input, or when you notice the same subproblem being solved repeatedly, either convert to an iterative loop or add memoization.

Common mistakes#

• Forgetting the base case entirely, or writing one that can never actually be reached from certain inputs — both lead to infinite recursion and an eventual crash.
• Not shrinking the problem on every recursive call. If a recursive case ever calls itself with the exact same input (or a larger one), it will never terminate, no matter how correct the base case is.
• Ignoring overlapping subproblems. Fibonacci's naive version is the textbook example — always ask "am I about to solve the same smaller problem more than once?" before assuming plain recursion is efficient enough.
• Using recursion for simple, large-scale iteration where a plain for loop would be clearer, faster (no function-call overhead per step), and immune to stack depth limits.