Thinking Recursively
A function that calls itself, like nesting dolls opening one inside another: the base case that stops it, and the call stack that keeps track, in pictures.
Updated
Recursion
- How Big Is This Folder? Recursion (Apprentice): Work out how big a folder is when it holds folders, which hold more folders, as deep as anyone made them: why one loop, a loop in a loop and a loop per level all come up short, and the idea that fixes them, recursion.
- The Folder Tool That Never Stopped: Base Cases (Apprentice): Find out why the folder tool crashed on one customer's drive, and make every recursive function you write stop: why a bigger stack, catching the error and a depth limit all fall short, and the two rules of a base case that fix it.
- Where Do the Waiting Calls Wait? The Call Stack (Apprentice): Trace any recursive function by hand, and see why recursion that goes too deep runs out of room: how a program keeps every waiting call's own values and the way back to it, which a single variable or a single bookmark can't do.
Exercise: The Nesting Dolls
- Exercise: The Nesting Dolls (Apprentice): A toy shop's product page needs three numbers from each set of nesting dolls: how many dolls, the color of the smallest, and how much shelf they take side by side. Work each one out without a loop, name where each one stops, and let the tests check your answers.