← Back to Games

Fibonacci Forest

Visualize the exponential recursion tree of Fibonacci!

fib(n) = fib(n-1) + fib(n-2), base: fib(0)=0, fib(1)=1
fib(5) = ?
0
Total Calls
0
Redundant Calls
0
Unique Calls

🐢 Naive Recursion O(2^n)

Each call branches into two more calls, causing exponential explosion. 

function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

🚀 Memoization O(n)

Store computed values to avoid redundant calculations.

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