A function that calls itself
Some problems are naturally defined in terms of smaller versions of themselves: a directory contains files and more directories, a tree node has child trees, and "sort this list" can be answered by "sort each half, then merge." Recursion — a function calling itself on a smaller input — is the direct way to code that shape, and interviews assume you have it: trees, graphs, and divide-and-conquer are recursion territory. Without it, those traversals require managing an explicit stack of pending work by hand.
Every correct recursive function has two parts:
- a base case: an input small enough to answer immediately, with no further calls;
- a recursive case: reduce the problem, call yourself on the smaller version, and combine.
long long factorial(int n) { if (n <= 1) return 1; // base case return n * factorial(n - 1); // recursive case }
factorial(4) computes 4 * factorial(3), which computes 3 * factorial(2), down to factorial(1) returning 1 — then the multiplications resolve on the way back up: 1 → 2 → 6 → 24.
Code exercise · cpp
Run factorial(10). Then trace factorial(3) on paper: write each call on its own line, and mark where the base case stops the descent.
What actually happens: stack frames
Recursion works because of the machinery you met in lesson 4-1: every call gets its own set of parameters and locals. When factorial(4) calls factorial(3), the first call's n = 4 is not overwritten — a fresh frame with n = 3 is stacked on top of it, and the n = 4 frame sits paused, waiting for the result. The frames unwind in reverse order as each call returns. (Unit 6 names the memory region these frames live in: the stack.)
Two consequences follow directly from that mechanism:
- A missing or unreachable base case is fatal. Each call stacks another frame; the frames never unwind; the few megabytes reserved for them run out and the program crashes — a stack overflow. In C++ this is a hard crash, not a catchable exception like Python's
RecursionError. - Depth is bounded. Recursing a million levels deep will overflow the stack even with a correct base case. For deep linear recursions, prefer a loop; save recursion for branching structures like trees, where depth stays shallow (a balanced tree of a million nodes is only about 20 levels deep) and the code is dramatically clearer.
A second worked example, digit by digit: the digits of 1984 are its last digit (1984 % 10 = 4) plus the digits of 1984 / 10 = 198 (integer division from lesson 2-2 — it discards the last digit). The number 0 has digit sum 0: a ready-made base case.
Code exercise · cpp
Your turn: complete sumDigits so it returns the sum of n's digits recursively. sumDigits(1984) should print 22 (1 + 9 + 8 + 4).
Quiz
You write a recursive function but forget the base case. What happens when you call it?