Implementing the Fibonacci Sequence in JavaScript: Common Approaches and Variations

As a developer, you’ve likely encountered the task of writing a function to calculate values in the Fibonacci sequence. This classic problem often appears in coding interviews, typically asking for a recursive implementation. However, interviewers may sometimes request specific approaches. In this article, we’ll explore the most common Fibonacci sequence implementations in JavaScript.

What is the Fibonacci Sequence?

First, let’s refresh our memory. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It starts with 0 and 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Common Implementation Approaches

1. Recursive Approach

The most traditional request is for a recursive implementation:

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

While straightforward, this approach isn’t performant for large values of n. On a MacBook Pro i9 with 16 GB RAM, calculating the 40th Fibonacci number took about 1.5 seconds:

console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms

Attempting to calculate the 50th number caused the Chrome tab to become unresponsive.

2. Recursive Approach with Caching (Memoization)

The next variation of this question is to improve performance by adding a caching mechanism to our recursive implementation:

function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  if (cached[n]) {
    return cached[n];
  }

  cached[n] = 
    fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached);

  return cached[n];
}

This approach introduces a cached object with initial values for 0 and 1. For any given number, we first check if we've already calculated its Fibonacci value. If so, we return the cached result instead of recalculating it. Otherwise, we calculate that value and store it in cached.

The performance improvement is significant (due to the additional memory used, of course). Calculating the 40th Fibonacci number took ~0.02 ms:

console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms

3. Iterative Approach with a for Loop

Another common variation is implementing the Fibonacci sequence using a for loop:

function fibonacciWithIteration(n) {
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let prev = 0;
    let next = 1;
    let result = 1;

    for (let i = 2; i <= n; i++) {
        result = prev + next;
        [prev, next] = [next, prev + next];
    }
    return result;
}

This approach is much faster than the basic recursive method (the one without caching):

console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms

The iterative approach can handle very large input values efficiently:

console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e+292
VM325:23 With iteration: 0.5830078125 ms

Bonus: Returning the Fibonacci Sequence as an Array

Interviewers might also ask you to return the entire Fibonacci sequence up to the n-th number as an array. Let’s implement this using both recursive and iterative approaches.

Recursive approach

function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1] + arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]

This function works as follows:

1. For 0 and 1, we return hardcoded arrays.
2. For other cases:

• We get the sequence for the previous number and store it in arr.
• We calculate currentValue by summing the last two values of arr.
• We combine arr and currentValue in a new array and return it.

Iterative Approach

function fibonacciSequenceWithIteration(n) {
  if (n < 1) {
    return [0];
  }

  let prev = 0;
  let next = 1;
  const arr = [prev, next];

  for (let i = 2; i <= n; i++) {
    arr.push(prev + next);
    [prev, next] = [next, prev + next];
  }
  return arr;
}

console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]

This function works as follows:

1. If the input is 0, we return an array with only the element 0.
2. For other cases:

• We initialize prev and next variables to store the previous and next values.
• We create arr with initial values [0, 1].
• We iterate from 2 to n, pushing the sum of prev and next to arr in each iteration.
• We update prev and next values and continue to the next iteration.

Conclusion

While this article covers several common Fibonacci sequence implementations, it’s not an exhaustive list. If you’ve encountered other variations in interviews or your work, please share them in the comments!

Stay updated with the latest JavaScript and software development news! Join my Telegram channel for more insights and discussions: TechSavvy: Frontend & Backend.

以上是Implementing the Fibonacci Sequence in JavaScript: Common Approaches and Variations的详细内容。更多信息请关注PHP中文网其他相关文章！