The Fibonacci sequence begins 1, 1, 2, 3, 5, 8, 13, and continues with each term equal to the sum of the preceding two. Its growth is exponential. section 7.3
A direct recursive definition in C
size_t fib(size_t n) { if (n < 3) return 1; return fib(n-1) + fib(n-2); } The condition n < 3 supplies the first two values; otherwise the function evaluates two smaller calls and adds their results. A call such as fib(4) creates a branching tree of calls with three terminating leaf calls. In general, fib(n) induces Fₙ leaf calls. The direct translation is therefore easy to read but slow because the same values are recomputed. section 7.3
TAKEAWAY: improve the computation without changing the sequence.
- Cache previously computed values so recursive calls reuse results. section 7.3
- Track only two values in a small buffer and update them while recursing. section 7.3
