Fibonacci Number in JavaScript: Check your skill

The Fibonacci sequence is a classic problem that appears frequently in programming interviews and coding challenges. In this blog post, we’ll walk through how to calculate the n-th Fibonacci number using JavaScript, explore various approaches, and discuss their time and space complexities.

What is the Fibonacci Series?

The Fibonacci series is an ordered sequence of numbers where each number is the sum of the two preceding numbers. The series starts with 0 and 1, and continues indefinitely:

[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … ]

The n-th Fibonacci number is denoted as F(n) , where:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) ) for ( n >=2 )

Problem Statement

Write a function that returns the ( n )-th entry in the Fibonacci series.

Examples:

fib(4); // Output: 3
fib(7); // Output: 13

Initial Solution

Let’s start by implementing a solution that builds the Fibonacci sequence up to the ( n )-th term using an array.

function fib(n) {
  // Initialize the Fibonacci series array with the first two numbers
  const fibSeries = [0, 1];

  // Calculate the Fibonacci sequence up to the n-th number
  for (let i = 2; i <= n; i++) {
    fibSeries[i] = fibSeries[i - 1] + fibSeries[i - 2];
  }

  // Return the n-th Fibonacci number
  return fibSeries[n];
}

// Test cases
console.log(fib(4)); // Output: 3
console.log(fib(7)); // Output: 13

Explanation

1. Array Initialization: We start with the first two numbers of the Fibonacci sequence, [0, 1], in an array called fibSeries.
2. Iterative Calculation: For each number from 2 to ( n ), we calculate the next Fibonacci number by summing the two previous numbers.
3. Return the ( n )-th Entry: The last element of the array represents the ( n )-th Fibonacci number.

Time and Space Complexity

• Time Complexity: O(n) , since we iterate from 2 to ( n ).
• Space Complexity: O(n), as we store the entire sequence in the array.

Optimized Approach for Space Efficiency

The above solution works well, but we can further optimize the space complexity. Since we only need the last two numbers to calculate the next Fibonacci number, we can use two variables instead of storing the entire sequence.

Here’s the space-optimized solution:

function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  let prev = 0;
  let current = 1;

  for (let i = 2; i <= n; i++) {
    const next = prev + current;
    prev = current;
    current = next;
  }

  return current;
}

// Test cases
console.log(fib(4)); // Output: 3
console.log(fib(7)); // Output: 13

Explanation of the Optimized Approach

1. Base Cases: We check for ( n = 0 ) and ( n = 1 ), returning 0 and 1, respectively.
2. Two Variables: We use prev and current to represent ( F(n-2) ) and ( F(n-1) ), respectively.
3. Iterative Calculation: We calculate the next Fibonacci number as the sum of prev and current, then update the variables.
4. Return the Result: The value of current at the end of the loop is the ( n )-th Fibonacci number.

Time and Space Complexity

• Time Complexity: O(n) , as we iterate from 2 to ( n ).
• Space Complexity: O(1), since we only use two variables.

Alternative Approach: Using Recursion

A more intuitive approach is to use recursion, where the function calls itself to calculate the previous two Fibonacci numbers:

function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  return fib(n - 1) + fib(n - 2);
}

// Test cases
console.log(fib(4)); // Output: 3
console.log(fib(7)); // Output: 13

Explanation of the Recursive Approach

1. Base Cases: When ( n = 0 ) or ( n = 1 ), return 0 or 1, respectively.
2. Recursive Call: For ( n >= 2 ), return the sum of fib(n-1) and fib(n-2).

Drawbacks of the Recursive Approach

• Time Complexity: (O(2^n) , as each function call generates two more recursive calls, leading to an exponential growth in the number of calls.
• Space Complexity: O(n) , due to the recursive call stack.

The recursive solution is less efficient for large ( n ), but it’s useful for understanding the nature of the problem.

Memoization: Improving the Recursive Solution

To overcome the inefficiency of the naive recursive approach, we can use memoization to store the results of previously calculated Fibonacci numbers.

function fib(n, memo = {}) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  if (memo[n]) return memo[n];

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

// Test cases
console.log(fib(4)); // Output: 3
console.log(fib(7)); // Output: 13

Explanation of Memoization

1. Base Cases: Return 0 or 1 if ( n = 0 ) or ( n = 1 ).
2. Memoization Check: If the result for the current ( n ) is already in the memo object, return it.
3. Store Results: Calculate the Fibonacci number and store it in memo to avoid redundant calculations.

Conclusion

Finding the ( n )-th Fibonacci number is a great exercise to learn about different algorithmic approaches, such as iterative solutions, recursion, and memoization. Each method has its pros and cons, and choosing the right one depends on the specific problem constraints.

Key Takeaways

1. Iterative Approach: Efficient and easy to understand; works well for most cases.
2. Space Optimization: Reducing space complexity by using only two variables.
3. Recursive Approach: Intuitive but can be inefficient due to redundant calculations.
4. Memoization: Combines the benefits of recursion and iteration for efficient computation.