Recursive Thinking

This is the skill that lets you break big problems into smaller copies of themselves — the pattern behind the 'deep' in deep learning, the way file explorers show folders inside folders, and the way ChatGPT plans a multi-step answer. Once you can think recursively, you can: write loops without off-by-one errors, understand how neural networks assemble predictions from layers (each layer a smaller computation), and reason about why an AI system doesn't blow up when it processes a long sentence (it does the same thing to each word). This page builds the mental habit; the next pages turn it into code (Base Cases and Recurrence) and then into the search that powers puzzle-solving and game AI (Depth-First Search with Backtracking).

You already know how to solve a problem by doing one small step and then repeating it. Recursion is the same, except instead of repeating the *same* step on the *same* problem, you repeat it on a *smaller* version of the problem, until the problem becomes so small that you can solve it instantly. The trick is to define the problem in terms of itself — to say 'to solve this, first do this smaller version, then combine the answers.' That sounds circular, and it is, but with one escape hatch: a 'base case' that has no smaller version, so the circle stops. The hard part is not writing the code — it is *seeing* that a problem can be split this way. Once you see it, the code follows. The thinking comes first: name the base case, name the shrinking argument, and trust that the smaller version will take care of itself.

Think of a Russian nesting doll — the matryoshka. You have a big doll. To get to the smallest doll, you open the big one, take out a slightly smaller one, open that, and so on, until you find a tiny solid doll that cannot be opened. That tiny doll is your base case. The action 'open and take out the next doll' is the recursive step. The whole process is recursion: each doll contains a smaller copy of itself, and you keep applying the same 'open' action until you hit the bottom. But here is where the analogy stops: in a real matryoshka, you open a doll to find *one* smaller doll. In recursion, the 'smaller problem' might be two smaller problems — like a family tree, where each parent has two children, and to count the whole tree you count the left branch and the right branch. Also, a real doll is a physical object; recursion is a *mental* framing. The doll analogy makes the idea of 'smaller self' vivid, but the real power is that you can apply the same reasoning to *any* problem that can be broken into smaller versions of itself — even if the 'smaller version' is not a physical thing.

Recursive thinking is the habit of defining a problem in terms of a smaller instance of itself, with a clear base case that stops the descent and a clear rule that relates a problem to its smaller version — before writing any code.

You have not studied recursion before, but you have used arithmetic: to add a list of numbers, you add the first to the sum of the rest. That is the seed. This page introduces the pattern; the library's Base Cases and Recurrence topic makes it precise (the 'recurrence relation' is the rule that connects a case to a smaller one, and it is also what you use to count how many steps an algorithm takes). The Stack Memory Behaviour topic will show you the cost of each recursive call — each one uses a little memory, and too many can overflow. Tail Recursion is a special case where the recursive call is the last thing done, which some languages turn into a loop. Tower of Hanoi is the classic puzzle whose solution is three lines of recursion. All of these depend on the habit you are building here: name the base case and the shrinking argument first.