Recursion.
Nesting dolls: solve a problem by doing the same smaller version of it, until one is tiny enough to answer outright.
Picture a set of Russian nesting dolls. To open the whole set you open one doll, which reveals a smaller doll, which you open to reveal a smaller one still — the same action, repeated on something smaller each time, until you reach the tiny solid doll that does not open.
Recursion is a function that solves a problem by calling itself on a smaller piece of the same problem. It keeps shrinking the job until it hits a case small enough to answer directly — the “base case” — then builds the full answer back up.
- Open this.1
A big problem. The trick: it contains a smaller version of the very same problem.
- 2
So do the same job — on the smaller piece.
- 3
Each step stacks up, waiting, as the problem gets smaller and smaller.
- This one I just know.4
Until the smallest case, simple enough to answer outright — the base case.
- 5
Now the answers travel back up, each step finishing once the piece below it is solved.
- Uh oh — no bottom.6
Forget the base case and it never stops — it just shrinks forever (stack overflow).
The two parts every recursion needs
Every recursive solution has two pieces: a base case that can be answered without recursing, and a recursive step that does a little work and then calls itself on something smaller. Miss the base case and it runs forever; fail to shrink the problem and it never reaches the base case.
Why a deep recursion can crash
Each call waits for the one below it, and each waiting call takes a little memory (a stack frame). Go too deep and that stack runs out of room — the famous “stack overflow.” Problems that nest very deep are often rewritten as a loop, which keeps the same idea without piling up frames.