Improving the performance of the recursive Fibonacci implementation using closures in JavaScript
If you ever encountered yourself doing some practice on recursion, I’m quite sure you faced the Fibonacci sequence algorithm. If you are not familiar with this problem, take a look at what Wikipedia has to say about it:
In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence called the Fibonacci sequence, such that each number is the sum of the two preceding ones.
So, if we start with 0 and 1, this is how the first N Fibonacci numbers look like:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...As you can see, each number (apart from the first two) is derived from the sum of the previous 2. For example, 13 is the result of adding 8 and 5.
In this article, we will develop a solution in Javascript using recursion, and we will improve its performance using closures.
First solution
Let’s try to code a function that will receive a number n, and will retrieve the Fibonacci number at the n position. We will use the recursive approach:
function fibonacci(n) {
if (n <= 0) {
return 0;
} else if (n <= 2) {
return 1;
} return fibonacci(n - 1) + fibonacci(n - 2);
}
(Note that some theories omit the first 0 from the Fibonacci sequence, in which case all you have to do is to omit the first if statement and change the second one to be n < 2 )
Pretty simple, huh? Let’s create some tests cases:
console.log(fibonacci(0)); // 0
console.log(fibonacci(1)); // 1
console.log(fibonacci(2)); // 1
console.log(fibonacci(3)); // 2
console.log(fibonacci(4)); // 3
console.log(fibonacci(10)); // 55
console.log(fibonacci(20)); // 6765
console.log(fibonacci(30)); // 832040
console.log(fibonacci(40)); // 102334155Which is great! Now, if you were to execute that in your browser, you’ll see that it gets slower and slower as the parameter n is incremented. This is because, for each time a call to fibonacci is made, 2 more calls to the same function are being done (except when n ≤ 2). This is called exponential complexity and is represented by O(2^n).
How can we reduce this complexity, without removing the recursion? To test this, we will first create some basic benchmarking using our old friend console.log.
Benchmarking
Let’s stay with that solution and add some logging to see how many times our function was executed:
let timesExecuted = 0;function fibonacci(n) {
timesExecuted++;
if (n <= 0) {
return 0;
} else if (n <= 2) {
return 1;
} return fibonacci(n - 1) + fibonacci(n - 2);
}const result = fibonacci(40);console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 204668309
Can you notice something? For a number as small as 40, we got more than 200 million executions, which is impossible to scale and will require an enormous CPU to process for bigger numbers.
How can we improve this? Let’s take a look at our example and see what happens internally, and we will try to find a part that can be done more efficiently.
------------------
fibonacci(40)
------------------
timesExecuted = 1fibonacci(39)
fibonacci(38)
------------------------------------
fibonacci(39)
------------------
timesExecuted = 2fibonacci(38)
fibonacci(37)
------------------------------------
fibonacci(38)
------------------
timesExecuted = 3fibonacci(37)
fibonacci(36)
------------------...
You can notice that the statements marked with bold will be executed more than once, and this will cause a lot of unnecessary calls that we can avoid somehow storing those results somewhere. What can we use?
Memoization
There’s a way in which we can use closures to store the results of some of those executions and avoid processing them again later. For this, we can use memoization:
Is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls.
Basically, before using recursion to get the nth Fibonacci number, we will search in memory to see if that value was previously calculated and then use it, like a cache.
Now, we will change our code a little bit to support this:
let timesExecuted = 0;function fibonacci(n) { const innerFibonacci = m => {
timesExecuted++;
if (m <= 0) {
return 0;
} else if (m <= 2) {
return 1;
} else {
return innerFibonacci(m - 2) + innerFibonacci(m - 1);
}
}
return innerFibonacci(n);
}const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 204668309
As you can see, we now defined a function innerFibonacci that will be in charge of calculating the value, and we now have a wrapper called fibonacci, which is the function that will be executed initially and the one that will return our result.
With this, the next step is to create a storage variable inside our wrapper function to store our partial results and check if there’s a previously calculated value before computing new values.
This is how it would look:
let timesExecuted = 0;function fibonacci(n) {
const fibonacciCache = new Map();
const innerFibonacci = m => {
if (fibonacciCache.has(m)) {
return fibonacciCache.get(m);
} else if (m <= 0) {
timesExecuted++;
return 0;
} else if (m <= 2) {
timesExecuted++;
return 1;
} else {
const resultInner = innerFibonacci(m - 2) + innerFibonacci(m - 1); timesExecuted++;
fibonacciCache.set(m, resultInner);
return resultInner;
}
} return innerFibonacci(n);
}const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 41
Can you believe it? 41 times vs 200 million times, that’s incredible. We are using a javascript Map to store our data, but you can use a native Object if you wish, or whatever data structure you like the most. There’s still some room for improvement though. We can try to remove the timesExecuted++ and a few ifs to avoid repetition, and we can sort things a little bit better.
Let’s try doing it:
function fibonacci(n) {
const fibonacciCache = new Map();
// Predefined values
fibonacciCache.set(0, 0);
fibonacciCache.set(1, 1);
fibonacciCache.set(2, 1);
const innerFibonacci = m => {
if (fibonacciCache.has(m)) {
return fibonacciCache.get(m);
} else {
const resultInner = innerFibonacci(m - 1) + innerFibonacci(m - 2); timesExecuted++;
fibonacciCache.set(m, resultInner); return resultInner;
}
} return innerFibonacci(n);
}const result = fibonacci(40);
console.log(result); // 102334155
console.log(`Times executed: ${timesExecuted}`); // 38
With this new change, we are defining some values in our memoization cache so we can remove some if statements, and also, we are reducing our number of executions from 41 to 38. Easy!
Conclusion
Even though this is not the best solution for a Fibonacci algorithm, it can be useful to learn recursion and its complications. Also, with this implementation, you can have a little more knowledge of memoization and how can it help you improve the performance of your apps.
Do you think there’s a way to reduce the number of executions even more using this implementation? How would you change to make it even more performant?
