Fibonacci: Iterative, Recursive, Memoized, Generator
Fibonacci is the canonical exercise for comparing iteration, recursion, memoization, and lazy evaluation. The iterative for-loop is the production answer, naive recursion is the cautionary tale (exponential cost), memoization fixes the recursion to linear time, and a generator yields an infinite stream you can `take(n)` from. Above index 78, switch to BigInt to avoid floating-point precision loss.
809 views
14
// O(n) time, O(1) extra memory.
const fibIterative = (n) => {
if (n < 0) throw new Error('n must be non-negative');
if (n < 2) return n;
let prev = 0;
let curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
};
console.log(fibIterative(0)); // 0
console.log(fibIterative(1)); // 1
console.log(fibIterative(10)); // 55
console.log(fibIterative(20)); // 6765
console.log(fibIterative(50)); // 12586269025
// Build the first n+1 numbers as a sequence.
const fibSequence = (n) => {
const seq = [0, 1];
while (seq.length <= n) seq.push(seq.at(-1) + seq.at(-2));
return seq.slice(0, n + 1);
};
console.log(fibSequence(8)); // [0, 1, 1, 2, 3, 5, 8, 13, 21]Two variables (prev and curr) are all you need. Each iteration shifts forward: the destructuring assignment swaps them in one step without a temporary. Time is O(n) and extra memory is O(1). The sequence variant returns the full prefix as an array, useful when the caller wants to render every step or feed them into a chart. Above n = 78, the result exceeds Number.MAX_SAFE_INTEGER (2^53 - 1) and you start losing precision; promote to BigInt (0n, 1n, prev + curr) for arbitrary-precision integers.
// Exponential time, ~O(phi^n) ≈ O(1.618^n). Each call branches into two
// subcalls, so fib(40) does over 200 million calls.
const fibNaive = (n) => {
if (n < 0) throw new Error('n must be non-negative');
if (n < 2) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
};
console.log(fibNaive(0)); // 0
console.log(fibNaive(10)); // 55
console.log(fibNaive(20)); // 6765
// Do NOT call fibNaive(40) in a hot loop or in production:
// fib(40) -> fib(39) + fib(38)
// fib(39) -> fib(38) + fib(37)
// each fib(38) is recomputed independently, billions of redundant calls.This is the textbook recursive definition: fib(n) = fib(n-1) + fib(n-2) with base cases at 0 and 1. It is short and faithful to the math, but the call tree branches into two subcalls per node, so the total number of calls grows like the Fibonacci numbers themselves (the closed-form is roughly phi^n where phi ≈ 1.618). At n = 40 you are already at 200+ million calls. Show this form to explain why memoization or iteration matter, then switch to one of those for any real workload.
// Closure-cached helper. Each fib(k) is computed once and reused.
const fibMemo = (() => {
const cache = new Map();
cache.set(0, 0);
cache.set(1, 1);
return function fib(n) {
if (n < 0) throw new Error('n must be non-negative');
if (cache.has(n)) return cache.get(n);
const value = fib(n - 1) + fib(n - 2);
cache.set(n, value);
return value;
};
})();
console.log(fibMemo(10)); // 55
console.log(fibMemo(50)); // 12586269025
console.log(fibMemo(70)); // 190392490709135
// Generic memoize-by-first-arg HOF (works for any pure n->v function).
const memoize = (fn) => {
const cache = new Map();
return (n) => {
if (cache.has(n)) return cache.get(n);
const v = fn(n);
cache.set(n, v);
return v;
};
};Memoization keeps the recursive structure but adds a cache of already-computed results. The IIFE wraps a Map cache that lives across calls; pre-seeding cache.set(0, 0) and cache.set(1, 1) covers the base cases without explicit if branches. Time drops to O(n) because each fib(k) is computed once and reused. The generic memoize HOF works for any pure single-arg function and is the building block for typical "don't recompute" patterns. Watch out for memory: an unbounded cache holds every computed value forever; use a bounded LRU if the input space is large.
// Lazy: the generator never finishes; the caller decides how many to consume.
function* fibStream() {
let a = 0;
let b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
// take(n) consumer: pull the first n values from any iterable.
const take = (iter, n) => {
const out = [];
let i = 0;
for (const v of iter) {
if (i >= n) break;
out.push(v);
i++;
}
return out;
};
console.log(take(fibStream(), 10));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
// Or pick the nth without building an array.
const fibAt = (n) => {
const it = fibStream();
let v;
for (let i = 0; i <= n; i++) v = it.next().value;
return v;
};
console.log(fibAt(20)); // 6765A generator function (function*) lets you describe an infinite sequence whose values are produced on demand, one yield at a time. The Fibonacci generator above never returns; the caller controls how many values to pull via take(n) or by consuming the iterator directly. This is the most flexible form: same shape works for prime streams, range generators, or any sequence where you do not know the length up front. Pair it with the iterator helpers proposal (map, filter, take becoming standard methods on iterators) once your runtime supports them.