First PrinciplesStart anywhere. Prove it, then move on.

Rung 25

Recursion

A procedure that calls itself and terminates anyway.

Best attempted after 14. Proof technique. Nothing stops you trying this now — the gate will tell you if you were right.

The gate

Solve one problem both recursively and iteratively, and show the two agree on many inputs. Name your base case and prove the recursive case always moves toward it. Then remove the base case deliberately, watch it fail, and explain what ran out.

Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.

A function that calls itself sounds circular, and would be, without one thing: a case that does not recurse. Every recursion is a promise that the problem gets smaller each time and that shrinking eventually stops.

If that sounds like rung 14, it is. Induction proves a base case and a step that assumes the smaller case. Recursion computes a base case and a step that calls the smaller case. Same shape, one proving and one running.

Why this is on the ladder

Because rung 26's trees are recursive objects — a tree is a node with subtrees — and code that walks them is far clearer written recursively. And because rung 45's backpropagation is a recursive traversal of the network's structure, whether or not it is written with a self-calling function.

Do this

Write factorial both ways. Recursively: n! is n times (n-1)!, with 0! = 1 as the base. Iteratively: a loop and an accumulator. Check they agree for many inputs.

Then watch the recursion in Python Tutor. See the frames pile up on the way down and unwind on the way back. That picture is what the stack is, and having seen it makes the failure below legible.

Now break it. Delete the base case and call it. You get a RecursionError — the interpreter stopped you before memory did. Say precisely what accumulated: one stack frame per call, each holding its own local state, none able to return until the one below it does.

Then find your machine's limit with sys.setrecursionlimit, and reason about why a limit exists at all.

Where people get stuck

Base case present but unreachable — recursing on n - 2 from an odd n toward a base of 0, sailing straight past it. The base case must be reachable from every input, which is exactly the "moves toward it" clause in the gate.

The other difficulty is trusting it. Recursion feels like it should not work, and people add defensive scaffolding that obscures the logic. Assume the recursive call does its job correctly — that assumption is the inductive hypothesis from rung 14, and it is licensed for the same reason.

Reading