Recursion

A function that calls itself

Recursion is a problem-solving technique where a function calls itself on a smaller version of the same problem. It shines when a problem has a naturally self-similar structure: trees, divide-and-conquer, mathematical definitions.

The two required parts

Every correct recursive function has two pieces:

• Base case — the smallest input, answered directly without recursion. This stops the chain.
• Recursive case — calls the function on a strictly smaller input, moving toward the base case.

// Factorial: n! = n × (n−1)!, with 0! = 1
int factorial(int n) {
  if (n <= 1) return 1;          // base case
  return n * factorial(n - 1);   // recursive case
}

Forget the base case and the function calls itself forever — until the stack overflows.

The call stack

Each recursive call pushes a new frame onto the call stack. For factorial(4) the stack grows like this:

factorial(4)
  → 4 × factorial(3)
        → 3 × factorial(2)
              → 2 × factorial(1)
                    → 1        // base case returns

Then the stack unwinds: 2×1=2, 3×2=6, 4×6=24. Every recursive solution uses O(depth) stack space — which is why extremely deep recursion fails.

Fibonacci: a cautionary tale

int fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);   // two recursive calls
}

This naïve Fibonacci is O(2ⁿ) — it recomputes the same values exponentially many times. The fix is memoization (caching results) or rewriting as iteration, both of which make it O(n).

Tail recursion

A function is tail recursive when the recursive call is the very last thing it does — nothing wraps the result. Some compilers (notably in functional languages like Scheme or Haskell) can optimize this into a loop, reusing one stack frame and avoiding overflow:

// Tail-recursive factorial: accumulator carries the result
int fact(int n, int acc) {
  if (n <= 1) return acc;
  return fact(n - 1, n * acc);   // nothing wraps the call
}

Any recursive algorithm can be rewritten as a loop with an explicit stack. Recursion is a tool for clarity, not speed — reach for it when the problem is naturally recursive (trees, backtracking, divide-and-conquer), and prefer iteration when depth is large or performance is critical.