A lesson from the Algorithms & Patterns module of the bootcamp. About a 12 minute read.
A function that calls itself on a smaller version of the problem. The mechanics take five minutes to learn. The mental shift is the whole lesson: you stop tracing what the machine does and start writing down a claim, assuming it holds one size smaller, and showing that it therefore holds here. Recursion is proof by induction that runs, and people who find it hard are almost always trying to simulate it in their head.
Every recursion has two parts. A BASE CASE says what the answer is when the problem is small enough to answer outright. A RECURSIVE CASE reduces a bigger problem to one or more smaller ones and combines their answers. The part that feels like cheating is the middle: you write the recursive call and assume it returns the right answer. That assumption is not wishful thinking. It is the inductive hypothesis. If the base case is correct, and the recursive case is correct GIVEN a correct answer one size down, then by induction the whole thing is correct at every size, and you never had to trace a single call. Do not step through three levels of calls to convince yourself. Check the base case, check the combining step, and stop.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 576 practice puzzles