Recursion: Functions Calling Themselves

Recursion is a technique where a function solves a problem by calling itself with a smaller or simpler input. Every recursive function has two parts:

1. Base case — the condition that stops the recursion. Without it, the function calls itself forever.
2. Recursive case — the function calls itself with a smaller input, then combines the result.

A Concrete Example: Factorial

The factorial of n (written n!) is the product of all positive integers up to n:

n! = n × (n − 1) × (n − 2) × ... × 2 × 1
0! = 1

Here is a recursive implementation:

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

When you call factorial(5), here is what happens:

• factorial(5) calls factorial(4)
• factorial(4) calls factorial(3)
• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1)
• factorial(1) calls factorial(0) — base case reached, returns 1
• Each call then returns: 1 → 1 → 2 → 6 → 24 → 120

See the full execution trace.

The Call Stack

Each function call creates a stack frame — a region of memory storing the function's local variables, parameters, and return address. When factorial(5) calls factorial(4), both frames exist simultaneously on the call stack. When factorial(0) returns, its frame is popped, and factorial(1) resumes.

This is why recursion has a memory cost proportional to the depth of the call tree — O(n) stack space for factorial(n). In a language without tail-call optimization, a sufficiently deep recursion will cause a stack overflow.

When Recursion Shines

Recursion is natural for problems that decompose into similar subproblems:

For binary trees and graphs, recursion mirrors the data structure's recursive definition, making the code far more readable than an iterative equivalent.

Common Pitfalls

1. No base case — infinite recursion, stack overflow.
2. No progress toward the base case — factorial(n) calling factorial(n) instead of factorial(n-1).
3. Computing the same subproblem repeatedly — naive Fibonacci recalculates fib(n-2) many times. A memo (cache) or bottom-up approach avoids this.
4. Stack overflow on deep recursion — for very large n, an iterative solution or an explicit stack is safer.

Key Takeaways

1. Every recursive function needs a base case and a recursive case that makes progress.
2. Each call adds a frame to the call stack — O(depth) memory.
3. Recursion excels at tree/graph problems and divide-and-conquer strategies.
4. Watch for redundant computation and stack overflow.

Try It Yourself

Implement recursive Fibonacci, then optimize it with memoization. See the climbing-stairs practice for a related dynamic programming exercise.

This article is part of the Algorithms Intermediate learning path.