Recursion Fundamentals

Recursion is a problem-solving technique where a function calls itself with a smaller version of the same problem. It feels strange the first time you see it — how can a function call itself? — but once you trust the pattern, recursive solutions are often shorter and clearer than the iterative equivalents.

The Two Parts of Every Recursive Function

Every correct recursive function has exactly two parts:

Base case — the smallest version of the problem, solved directly without recursion. For factorial, that's factorial(0) = 1. For walking a list, it's the empty list.
Recursive step — express the answer in terms of a smaller subproblem, then call yourself on it. For factorial: n * factorial(n - 1).

If you forget the base case, you get infinite recursion and a stack overflow. If your recursive step doesn't make the problem smaller, same result. Always check both.

The Call Stack

Each function call gets its own slot on the call stack — a stack of frames where local variables and return addresses live. When factorial(5) calls factorial(4), a new frame goes on top; when factorial(4) returns, that frame pops off and control returns to factorial(5).

This is why deep recursion can crash with "stack overflow." Languages typically allow only a few thousand frames before they run out of room.

Recursion vs Iteration

Anything you can do with recursion you can do with a loop, and vice versa. The choice is often about clarity. Tree and graph traversals, divide-and-conquer algorithms, and problems with branching choices feel natural recursively. Simple counting and accumulation usually feel cleaner with a loop.

A Warning About Naive Fibonacci

Naive recursive Fibonacci is exponential — fib(40) makes over a billion calls because subproblems get re-solved. Fix it with memoization (cache results) or iteration (build up from the base case). Recursion is a tool; like all tools, it has trade-offs.

Try It Yourself

Write a recursive function to compute the power: pow(x, n) = x * pow(x, n-1)
Reverse a string recursively: take the first character and append it to the reverse of the rest
Add memoization to fib so it doesn't recompute the same values