Introduction to Recursion

Introduction to Recursion

Recursion is what happens when a function solves a problem by calling itself on a smaller version of the same problem, then combining the answers. The mental trick is to stop imagining the whole computation at once. Instead you make a promise: "If I already had the answer to a slightly smaller input, could I build the answer to this one in one step?" If yes, you write that one step and trust the function to handle the smaller input the same way. That leap of faith is sometimes called the recursive leap of faith, and it is the single hardest habit to build.

A classic picture is a set of Russian nesting dolls: to count all the dolls, you open the outer one (that is 1), and add however many dolls are inside. You do not need a special rule for the inside — it is the same problem, just smaller. Eventually you reach the tiniest solid doll that contains nothing. That final doll is the part that keeps recursion from running forever.

Precise definition

A recursive function must have two ingredients, and interviewers will check for both:

• Base case — one or more inputs so small the answer is known outright, with no further self-call. This is the tiniest doll. Miss it and you get infinite recursion, which in practice ends in a StackOverflowError (Java) or RecursionError (Python), because each pending call occupies a frame on the call stack.
• Recursive case — reduce the input toward the base case and call the function on that smaller input, then use its result. The reduction must be monotone: every call must strictly approach the base case, or termination is not guaranteed.

Formally: f(n) is defined in terms of f applied to inputs strictly "closer" to a base case under some well-founded ordering (a measure that cannot decrease forever). Recursion is the direct code expression of a recurrence relation, e.g. fact(n) = n × fact(n−1), fact(0) = 1.

Worked example: factorial(4), operations counted

Define fact(n) = 1 if n ≤ 1 (base), else n × fact(n−1). Watch the two phases. First the calls wind down, each pushing a frame that waits on the one below it:

• fact(4) needs 4 × fact(3) → suspends, pushes a frame
• fact(3) needs 3 × fact(2) → suspends
• fact(2) needs 2 × fact(1) → suspends
• fact(1) hits the base case → returns 1 (no self-call)

Then results unwind back up, and only now do the multiplications actually run: fact(2)=2×1=2, fact(3)=3×2=6, fact(4)=4×6=24. Count it honestly: 4 calls made, maximum stack depth 4, and exactly 3 multiplications — deferred until the unwinding. That deferral is the whole point: the pending work lives on the stack, not in a loop variable. Time is O(n), and the extra memory for the stack is also O(n) — an iterative loop would be O(1) space.

Common pitfalls & what an interviewer probes

• Missing or unreachable base case. The reduction must actually hit it. fact(n−2) from an odd n skips n=1 and never stops. Interviewers ask "what makes this terminate?" — answer with the decreasing measure.
• Redundant recomputation. Naive fib(n) = fib(n−1) + fib(n−2) recomputes the same subproblems and runs in O(φⁿ) exponential time — fib(40) makes ~330 million calls. The fix (memoization / dynamic programming) is a favorite follow-up.
• Stack overflow on deep recursion. Depth is bounded by the stack (~thousands of frames in Java/Python). A loop over a 10⁶-element list recursed naively will crash where iteration would not.
• Mutating shared state across calls. Passing a growing accumulator or list by reference and forgetting to undo changes (in backtracking) is a classic bug. Interviewers watch whether you reason about what each frame owns.
• Confusing the two phases. Work done before the recursive call (pre-order) versus after it returns (post-order) gives different results — as the factorial multiplications showed.

When it matters in practice & trade-offs

Recursion is not about speed — it is about matching the shape of the data. Any recursion can be rewritten as a loop with an explicit stack, and vice versa, so they are equally powerful. You reach for recursion when the structure is itself self-similar: trees (traversals, parsing), graphs (DFS), divide-and-conquer (merge sort, quicksort, binary search at O(log n) depth), and backtracking (permutations, N-queens, sudoku). On these, recursive code is often half the length of the iterative version and far easier to prove correct.

The trade-off is the call stack: recursion spends O(depth) memory and a small per-call overhead that iteration avoids. For a straight sequence, a loop is strictly better — O(1) space, no overflow risk. Prefer recursion when depth is shallow or logarithmic (balanced tree of a billion nodes is only ~30 deep) and the code clarity is worth it; prefer iteration when depth can grow linearly with input. Note that tail recursion (the self-call is the last action) can be optimized into a loop by some compilers — but the JVM and CPython do not do this, so in Java/Python deep tail recursion still overflows.

Key takeaways

• Every recursion needs a base case (no self-call) and a recursive case that provably shrinks the input toward it.
• Pending calls stack up while winding down, then combine while unwinding — factorial(4) is O(n) time and O(n) stack space, with multiplications deferred to the return phase.
• Watch for the big three failure modes: no reachable base case, exponential recomputation (fix with memoization), and stack overflow on linear depth.
• Choose recursion for self-similar structures (trees, divide-and-conquer, backtracking); choose iteration when recursion depth grows linearly with input size.