Dynamic Programming: Optimal Substructure and Overlapping Subproblems

Recursion means a function solves a big problem by calling itself on a smaller version of the same problem. Picture moving a stack of rings from one peg to another. To move three rings, you first move the top two rings out of the way, move the bottom ring, then move the two rings back on top. Moving the two rings is itself done by moving one ring out of the way, moving the next, then moving the one ring back. The same small job shows up again and again inside the big job. Every recursive solution needs two parts. First, a base case: the smallest problem you can answer directly, like moving a single ring. Second, a recursive case: how a bigger problem breaks into smaller ones plus a little extra work. Without a base case the function calls itself forever. Note the contrast that decides everything: moving rings never repeats the same subproblem, each smaller move happens once, so storing answers saves nothing there. Fibonacci is the opposite. Its recurrence fib(n) = fib(n-1) + fib(n-2) recomputes the same values exponentially many times, so when the same smaller problem keeps reappearing, storing each answer once saves huge amounts of work.

This section shows recursion working on everyday data like words and lists. A word that reads the same forwards and backwards, like racecar, is a palindrome. You can check one recursively. Strip the first and last letters. If they do not match, the answer is no. If they do match, ask the same question about the word left in the middle, which is shorter. Keep going until the word has one or no letters left, which is the base case and means yes. Notice what happens: the same check runs on smaller and smaller pieces, and each piece is solved the same way as the original. That idea, a problem built from smaller versions of itself, leads to the two questions you should always ask about a problem: can its best answer be built from best answers to smaller versions, and do those smaller versions keep showing up more than once. When both answers are yes, remembering each answer once instead of recomputing it turns slow code into fast code.

Think Python is a friendly introduction to programming that builds one idea at a time and defines every term when it first appears. It matters for this topic because it introduces recursion as a sequence of small, careful steps rather than one big leap. You first learn that a function can call itself, then you see how a problem must shrink toward a base case each time, and only then do you meet harder uses like Fibonacci, where a simple recursive version recomputes the same values over and over and becomes terribly slow. That slow version is the perfect before picture. Once you can watch a recursive function redo the same smaller problem many times, you are ready to ask the two key questions: is the best answer to the big problem built from best answers to smaller versions, and do those smaller versions repeat. When both are true, saving each answer the first time you compute it turns an exponential tangle into a fast, polynomial one. Concretely, naive fib(20) makes over 20,000 calls because it recomputes the same small values again and again, while the memoised version computes each of fib(0) through fib(20) once, about 21 values, each in constant extra work. State the subproblem and the recurrence before any code, for example subproblem fib(k) for k below n with fib(k) = fib(k-1) + fib(k-2). When the method does not apply, name the failing condition: mergesort pieces are all distinct, so overlapping subproblems fails; the longest simple path reuses vertices, so optimal substructure fails.