What is recursion, really?

A recursive function calls itself — which sounds circular. How does that ever finish, and how should you think about what it's doing?

Imagine you're in a cinema queue and want to know your position. Ask the person ahead of you; they ask the person ahead of them; and so on until someone at the front says 'I'm first'. Then the answers flow back: 'I'm 1st' → 'so I'm 2nd' → 'so I'm 3rd' — down to you.

That's recursion: pass a smaller version of the question forward until someone can answer without asking (the base case), then combine the answers on the way back. It isn't circular, because every call asks a strictly smaller question.

A recursive definition has two parts: a base case answered directly, and a recursive case that reduces the problem toward the base. Factorial: fact(0) = 1; fact(n) = n × fact(n−1) for n > 0.

At runtime each call gets its own stack frame holding its own n; frames pile up until the base case, then unwind as each returns. Omit the base case (or fail to shrink the problem) and frames pile up forever — a stack overflow.

Anything recursive can be rewritten with a loop and vice versa; recursion earns its keep on self-similar structures — trees, nested folders, divide-and-conquer algorithms like merge sort.

Trace fact(4): fact(4) → 4 × fact(3) → 4 × (3 × fact(2)) → 4 × (3 × (2 × fact(1))) → 4 × (3 × (2 × (1 × fact(0)))). fact(0) hits the base case and returns 1, and the chain collapses upward: 1 → 1 → 2 → 6 → 24. Four frames down, four returns up.

• Forgetting the base case, or writing a recursive call that doesn't shrink the input — both recurse forever and crash the stack.
• Trying to hold the whole call tree in your head at once. Trust the function: assume fact(n−1) returns the right answer and check only that your step uses it correctly — that's exactly the reasoning of mathematical induction.

• Thinking recursively: base case + smaller subproblem (any introductory algorithms text, e.g. CLRS Ch. 2 & 4)
• Khan Academy — Recursive algorithms