Fibonacci Theory

1. Naïve Recursion (Exponential)

The direct translation of the recurrence leads to a binary recursion tree of size roughly 2^n because we recompute the same values many times.

function fib(n) {
  if (n <= 1) return n;      // F(0)=0, F(1)=1
  return fib(n-1) + fib(n-2); // Recomputes many subproblems
}

Time: O(2^n) — Space (recursion depth): O(n)

2. Memoization (Top-Down)

Store previously computed results in a cache. Each distinct subproblem F(k) is computed once.

function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  return memo[n];
}

Time: O(n) — Space: O(n) for recursion + cache.

3. Tabulation (Bottom-Up)

Build the solution iteratively from base cases upward. Eliminates recursion overhead.

function fibTab(n) {
  if (n <= 1) return n;
  const dp = Array(n+1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

Time: O(n) — Space: O(n)

4. Space Optimization (Rolling Variables)

Only the last two values are needed at any point, so we can reduce memory to constant space.

function fibOpt(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;        // F(0), F(1)
  for (let i = 2; i <= n; i++) {
    const c = a + b;       // F(i)
    a = b;                 // shift window
    b = c;
  }
  return b;                // F(n)
}

Time: O(n) — Space: O(1)

5. Complexity & Transitions

• Naïve recursion explodes: duplicate subtrees for each call.
• Memoization retains recursion structure but trims duplicates.
• Tabulation linearizes evaluation order explicitly.
• Space optimization observes only two previous states matter.

6. When To Use Which