Fibonacci: Recursive, Iterative, Matrix, and Golden-Ratio Forms

Why This Matters

Fibonacci is small enough to compute by hand and rich enough to show several algorithmic styles. The same recurrence can be exponential, linear, or logarithmic depending on representation.

Core Idea

The sequence satisfies:

$F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2}.$

Method	Time	Idea
naive recursion	exponential	recomputes subproblems
memoized recursion	$O(n)$	caches subproblems
iteration	$O(n)$	keeps last two values
matrix exponentiation	$O(\log n)$	repeated squaring
closed form	model-dependent	uses the golden ratio formula

Worked example: computing F_5 recursively recomputes F_3 more than once. Memoization stores it once.

Common Mistakes

Using naive recursion as if it were a reasonable implementation.
Treating the closed form as exact floating-point code for large $n$ .
Missing that matrix exponentiation is divide and conquer on powers.

Exercises

Draw the recursion tree for F_5.
Write the iterative state update for Fibonacci.
Explain why memoization changes the number of computed states.

Next Topics

References

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 4, 14.
Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 1.