A lesson from the data structures and algorithms bootcamp. About a 12 minute read.
A function that calls itself on a smaller version of the problem. The mechanics are five minutes of work and 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 it therefore holds here. Recursion is proof by induction with a runtime, and people who find it hard are almost always trying to simulate it in their head instead.
Every recursion is a BASE CASE saying what the answer is when the problem is small enough to answer outright, and a RECURSIVE CASE that 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 optimism, it is the inductive hypothesis. If the base case is correct, and if 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. Verify the base case, verify the combination step, and stop.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles