1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Naive recursive approach
function fibonacciRecursive(n) {
  // Base cases
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Recursive case
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
 
// Memoization approach (top-down dynamic programming)
function fibonacciMemoization(n) {
  // Create memoization table
  const memo = {};
  
  function fib(n) {
    // Check if we've already calculated this value
    if (n in memo) return memo[n];
    
    // Base cases
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Calculate and store the result
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
  }
  
  return fib(n);
}
 
// Tabulation approach (bottom-up dynamic programming)
function fibonacciTabulation(n) {
  // Handle base cases
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Create table
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  // Fill the table
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}
 
// Space-optimized iterative approach
function fibonacciOptimized(n) {
  // Handle base cases
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  let a = 0;  // F(0)
  let b = 1;  // F(1)
  let c;
  
  // Calculate Fibonacci numbers iteratively
  for (let i = 2; i <= n; i++) {
    c = a + b;  // F(i) = F(i-2) + F(i-1)
    a = b;      // Update F(i-2) for next iteration
    b = c;      // Update F(i-1) for next iteration
  }
  
  return b;
}
 
// Test cases
console.log(fibonacciRecursive(10));     // 55 (but slow for larger inputs)
console.log(fibonacciMemoization(10));   // 55
console.log(fibonacciTabulation(10));    // 55
console.log(fibonacciOptimized(10));     // 55
 
// Test with larger input (would be very slow with naive recursion)
console.log(fibonacciMemoization(40));   // 102334155
console.log(fibonacciTabulation(40));    // 102334155
console.log(fibonacciOptimized(40));     // 102334155