The problem. The Fibonacci numbers start F(0) = 0, F(1) = 1, and each one after is the sum of the two before it: F(n) = F(n − 1) + F(n − 2). Given n, return F(n).
n = 2 -> 1 (1 + 0)
n = 4 -> 3 (2 + 1)
n = 10 -> 55The problems in this chapter are recursion in its plainest form: a base case, one or two smaller calls, and a way to combine them. Each one also shows what recursion costs — the extra calls of tree recursion, the stack memory of a long chain of calls — and when a loop or a smarter split does better.
The call tree branches twice at every level, and the same small calls appear again and again.
function fib(n) { if (n <= 1) return n; // base cases: fib(0) = 0, fib(1) = 1 return fib(n - 1) + fib(n - 2); // two calls: the call tree branches}Time O(2ⁿ) (more precisely about 1.6ⁿ), space O(n) for the call stack. It's the textbook definition, but fib(40) already makes over 300 million calls.
The call tree is full of repeats: fib(n − 2) is computed inside fib(n − 1) and again on its own. Store each answer the first time it's computed and return the stored value after that. Now each fib(k) is computed once.
function fib(n, memo = new Map()) { if (n <= 1) return n; if (memo.has(n)) return memo.get(n); // computed before: reuse it const value = fib(n - 1, memo) + fib(n - 2, memo); memo.set(n, value); return value;}Time O(n), space O(n) for the memo and the call stack. This is top-down dynamic programming — the Dynamic Programming course starts exactly here.
function fib(n) { let prev = 0, cur = 1; // F(0), F(1) if (n === 0) return 0; for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur]; // slide one step forward return cur;}Time O(n), space O(1). Each value needs only the two before it, so two variables are enough. (A 2 × 2 matrix power reaches O(log n), but it's rarely asked.)
% m each step.