Fundamentals

Recursion, without the mystique

Short answer: a recursive function solves a problem by calling itself on a smaller version of the same problem, and stops at a base case small enough to answer directly. Two parts, always: base case and recursive step.

The two parts

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n <= 1) return 1;        // base case: answer directly
    return n * factorial(n - 1); // recursive step: smaller problem
}

int main() {
    cout << factorial(5) << endl;   // 120
    return 0;
}

Remove the base case and the function calls itself forever until the program runs out of stack. That failure mode has a name: stack overflow.

What actually happens, step by step

Recursion is not magic — it is a stack of paused calls. Each call waits for the one below it:

factorial(4)
  needs 4 * factorial(3)
    needs 3 * factorial(2)
      needs 2 * factorial(1)
        factorial(1) returns 1        ← base case reached
      returns 2 * 1 = 2
    returns 3 * 2 = 6
  returns 4 * 6 = 24

The chain builds up going down, then unwinds going back up. That is why the base case must be reachable — otherwise the chain never starts unwinding.

Recursion you can see: counting down

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n == 0) {           // base case
        cout << "liftoff" << endl;
        return;
    }
    cout << n << " ";
    countdown(n - 1);       // recursive step
}

int main() {
    countdown(5);
    return 0;
}

Note that the printing happens before the recursive call, so the numbers come out descending. Move the cout after the call and they come out ascending — that single reordering is the difference between "before the descent" and "after the return".

When recursion is the natural tool

Whenever the problem is defined in terms of itself. Tower of Hanoi is the cleanest example: move n disks = move n−1 aside, move the big one, move n−1 back.

#include <iostream>
using namespace std;

void hanoi(int n, int from, int to, int via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);
    cout << "move " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, via, to, from);
}

int main() {
    hanoi(3, 1, 3, 2);
    return 0;
}

Try tracing that by hand once. Notice you do not need to hold the whole sequence in your head to trust the code — you only need to believe that the two smaller calls work. That is the mental move recursion requires, and the practice problem Tower of Hanoi drills it.

Recursion vs loop

Any recursion can be rewritten as a loop with an explicit stack or an accumulator. Which to use:

The costs

• Stack space. Every pending call holds a frame. Depth 1,000,000 crashes; depth 40 is nothing.
• Recomputation. Naive recursive Fibonacci calls itself twice per level — about 2^n calls. Fibonacci shows the fix (carry two values).
• Base case must be reachable. A step that skips past the base (n -= 2 when the base checks n == 0) still overflows.

Interview follow-ups

1. What is a stack overflow? Too many nested calls; the call stack runs out of space. Almost always a missing or unreachable base case.
2. How would you convert this recursion to a loop? Identify the accumulator and the direction; for tree-shaped recursion you need an explicit stack.
3. Why is naive Fibonacci exponential? Because it recomputes the same subproblems — the classic case for memoisation or a bottom-up DP.

Practice: Tower of Hanoi, All Permutations, Fibonacci. Read next: stack vs heap explains where those paused calls actually live.