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:
- For 0 and 1, we return hardcoded arrays.
- 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 ofarr
. - We combine
arr
andcurrentValue
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:
- If the input is 0, we return an array with only the element 0.
- For other cases:
- We initialize
prev
andnext
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
andnext
toarr
in each iteration. - We update
prev
andnext
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.
Top comments (2)
Nice one! For those who want more context - artofproblemsolving.com/wiki/index...