Skip to content
Fibonacci – Iterative vs Recursive JS

Fibonacci – Iterative vs Recursive JS

Fibonacci – Iterative Solution

Time Complexity: O(n) time, O(1) space

Finds the nth Fibonacci number using iteration. Using a for loop we can get the n number by adding the previous numbers.

function iterativeFibonacci(n) {
  if (n < 0) return "Please enter a positive integer";
  if (n <= 1) return n;
  let one = 0,
    two = 1;
  for (i = 2; i < n; i++) {
    const next = one + two;
    one = two;
    two = next;
  }
  return two;
}

console.log(iterativeFibonacci(6));Code language: JavaScript (javascript)

Generate Fibonacci Series

Time Complexity: O(n) time, O(n) space

Generates the first n Fibonacci numbers:

function fibonacciSeries(n) {
  if (n <= 0) return [];
  if (n === 1) return [0];
  if (n === 2) return [0, 1];

  const fib = [0, 1];
  for (let i = 2; i < n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib;
}

console.log(fibonacciSeries(6)); // Output: [0, 1, 1, 2, 3, 5]Code language: JavaScript (javascript)

Fibonacci – Recursive Solution

Time Complexity: O(2ⁿ) time, O(n) call stack space

Use with caution – exponential time complexity:

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

console.log(fibonacciRecursive(6)); // 8Code language: JavaScript (javascript)

Call Stack Visualization:

              5
             / \
            4   3
           / \ / \
          3  2 2  1
         / \ / \
        2  1 1  0
       / \
      1   0                    Code language: JavaScript (javascript)

Recursive with Memoization

Time Complexity: O(n) time, O(n) space

Optimized using memoization to store computed values:

function fibRecursiveMemo(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }
  if (n <= 1) return n;
  memo[n] = fibRecursiveMemo(n - 1, memo) + fibRecursiveMemo(n - 2, memo);
  // console.log(memo); // Uncomment to see memoization progress
  return memo[n];
}

console.log(fibRecursiveMemo(6)); // 8 (6th Fibonacci number)Code language: JavaScript (javascript)

Memoization Progress:

{ '2': 1 }
{ '2': 1, '3': 2 }
{ '2': 1, '3': 2, '4': 3 }
{ '2': 1, '3': 2, '4': 3, '5': 5 }
{ '2': 1, '3': 2, '4': 3, '5': 5, '6': 8 }Code language: JavaScript (javascript)

Optimized Call Stack:

              fib(6)
            /       \
        fib(5)     fib(4) (cached)
       /      \
    fib(4)   fib(3) (cached)
   /     \
fib(3) fib(2) (cached)


// Detailed view with memo
             6 (memo: {6:8, 5:5, 4:3, 3:2, 2:1, 1:1, 0:0})
            / \
           /   \
          5 (memo: {5:5, 4:3, 3:2, 2:1, 1:1, 0:0})  4 (memo: {4:3, 3:2, 2:1, 1:1, 0:0})
         / \                                       |
        /   \                                       |
       4 (memo: {4:3, 3:2, 2:1, 1:1, 0:0}) 3 (memo: {3:2, 2:1, 1:1, 0:0})    2 (memo: {2:1, 1:1, 0:0})
      / \                                 / \
     /   \                               /   \
    3 (memo: {3:2, 2:1, 1:1, 0:0}) 2 (memo: {2:1, 1:1, 0:0}) 2 (memo: {2:1, 1:1, 0:0}) 1 (memo: {1:1, 0:0})
   / \                                  /\
  /   \                                /  \
 2 (memo: {2:1, 1:1, 0:0}) 1 (memo: {1:1, 0:0}) 1 (memo: {1:1, 0:0}) 0 (memo: {0:0})
 / \
/   \
1 (memo: {1:1, 0:0}) 0 (memo: {0:0})
Code language: JavaScript (javascript)

Which one is the fastest?

Iteration is the fastest since we do not re-compute values like in recursion. Additionally, the iterative approach is also memory efficient in terms of function calls and memory usage. However, recursion with memoization is almost as efficient as iteration when n is small.

n=10

  • Iterative method took: 0.04 ms
  • Recursive method took: 0.02 ms
  • Memoized Recursive method took: 0.03 ms

n=20

  • Iterative method took: 0.05 ms
  • Recursive method took: 0.96 ms
  • Memoized Recursive method took: 0.05 ms

n=40

  • Iterative method took: 0.07 ms
  • Recursive method took: 1477.80 ms
  • Memoized Recursive method took: 0.16 ms

Code to test performance

Comparison with performace.now():

function measureExecutionTime(fn, ...args) {
  const start = performance.now();
  fn(...args); // Execute the function
  const end = performance.now();
  return end - start; // Time taken in milliseconds
}

// Iterative Fibonacci
function iterativeFibonacci(n) {
  if (n < 0) return "Please enter a positive integer";
  if (n <= 1) return n;
  let one = 0,
    two = 1;
  for (i = 2; i < n; i++) {
    const next = one + two;
    one = two;
    two = next;
  }
  return two;
}

// Recursive Fibonacci
function fibonacciRecursive(n) {
  if (n <= 1) return n;
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// Recursive Fibonacci with Memoization
function fibRecursiveMemo(n, memo = {}) {
  if (n in memo) {
    return memo[n];
  }
  if (n <= 1) return n;
  memo[n] = fibRecursiveMemo(n - 1, memo) + fibRecursiveMemo(n - 2, memo);
  // console.log(memo); // Uncomment to see memoization progress
  return memo[n];
}

// Compare execution times
const n = 40; // Adjust `n` based on your test requirements

const iterativeTime = measureExecutionTime(iterativeFibonacci, n);
const recursiveTime = measureExecutionTime(fibonacciRecursive, n);
const memoizedTime = measureExecutionTime(fibRecursiveMemo, n);

console.log(`Iterative method took: ${iterativeTime.toFixed(2)} ms`);
console.log(`Recursive method took: ${recursiveTime.toFixed(2)} ms`);
console.log(`Memoized Recursive method took: ${memoizedTime.toFixed(2)} ms`);Code language: JavaScript (javascript)
Back to Top
Tags: