Fibonacci Number

Recursion · Define a small base case, then a smaller version · Warm-up · about 14 min

Why it matters

Trees, graphs, backtracking, and dynamic programming all become less scary after this idea.

How it connects

Binary search uses a repeated smaller range. Recursion makes “solve a smaller version” explicit.

Try first

Say the two smallest inputs aloud. What should the function return without calling itself?

Interview cue

The recursive definition is clear, but it repeats work; memoization can improve it later.