Recursion: relate the big problem to a smaller copy
Solve a problem of size $n$ by relating it to size $n-1$. The hard part is finding the recurrence, never solving it.
Method · Recursion
Intro
Rafael Ruggiero (User:Azulejoazul) — https://commons.wikimedia.org/wiki/File:Fractal_tree.gif · CC BY-SA 4.0 · Wikimedia Commons
Recursion solves a problem by relating $f(n)$ to smaller instances $f(n-1)$, $f(n-2)$, and so on. Find the boundary (the smallest case you can answer directly), express the recurrence (relate big to small), then walk up. The same three-step skeleton powers Fibonacci-style counting, Tower of Hanoi, expected values via first-step analysis, and most of the dynamic-programming half of FAANG interviews.
✓ Intro · expand
Try first (productive failure)
Before the worked example: spend 60 seconds taking your best shot at this.
A guess is fine — being briefly wrong about a problem makes the explanation
land harder when you read it. This appears once per tutorial; skip
if you already know the trick.
60s
✓ Try first · expand
Worked example
A rabbit climbs a staircase with 5 steps. It can hop up either 1 step or 2 steps at a time. How many distinct sequences of hops can the rabbit make to reach the top?
✓ Worked example · expand
Practice 1 of 3Type a fraction, decimal, or expression — mathjs parses it.
✓ Practice · expand
Reflection
When you saw a problem you’d never seen before, what was the cue that told you “this wants recursion”? In your own words, what makes a problem decompose cleanly into smaller copies of itself?
