Optimize Fibonacci with Dynamic Programming

What is the Fibonacci Sequence?

The Fibonacci sequence is a series of numbers in ascending order. Each number after the first two is a Fibonacci number that must be equivalent to the sum of the previous two numbers before it. For example, take this Fibonacci series of numbers from 0 to 610:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

So you may ask why is this useful? Well, Fibonacci is something that’s more so applied in the field of mathematics than it is in Programming. Although it is considered a useful tool for teaching things like recursion. It can also be used as a problem for introducing the concept of dynamic programming like we’ll be doing here.

Solving Fibonacci without Dynamic Programming

So, to begin to figure out how to solve the Fibonacci problem with Dynamic Programming, we should first know how to solve it with just plain recursion.

function fibonacci(n) {
    if (n < 2) {
        return n;
    }
    // get fibonacci number (sum of previous two nums)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

So this would give us our answer. But why is this not the optimal solution? We know that when using recursion, each function call gets pushed onto the call stack. For this specific problem, we can think of it as a recursion tree with many levels.

                      fibonacci(6)
                     /            \
                    f(5)          f(4) 
                  /     \         /   \
               f(4)     f(3)     f(3) f(2)
               /  \     /   \       / \
            f(3)  f(2) f(2) f(1)  f(2) f(1)
           /  \
        f(2)  f(1)

As you can see here we have several overlapping calculations happening from the recursive function calls. This means our solution is doing a lot of unnecessary work. This might be fine when solving for smaller numbers like 1 to 6 but as soon as we scale up to larger numbers it becomes a problem. To further see what I mean let’s add an incrementer variable to get the number of calculations performed.

let numCalculations = 0;

function fibonacci(n) {
    numCalculations++;
    if (n < 2) {
        return n;
    }
    // get fibonacci number (sum of previous two nums)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Now if we pass in 7 for example we’ll get 13 calculations. But let’s try a larger number like 20.

fibonacci(20); // 6765
console.log(numCalculations); // 21891

Woah! This gives us a whopping 21891 calculations. You might be thinking that can’t be good for the big O runtime of this solution. You’d be right! With this solution, we get a time complexity of O(2^n). Not very fast!

Implementing Dynamic Programming to solve Fibonacci

So what is Dynamic Programming first of all? Dynamic Programming is basically just an optimization technique. It’s commonly used on problems that have overlapping subproblems, just like our Fibonacci problem that is currently solving the same subproblems again and again.

To optimize our Fibonacci solution we’re going to use a Dynamic Programming technique called Memoization. This technique works by storing the result of our function calls inside of a data structure such as a hash map and then checking it on each recursive call to see if we’ve already calculated for that specific problem. Let’s implement this technique with our Fibonacci problem to optimize our solution.

function dynamicFibonacci() {
    let cache = {};

    return function fib(n) {
        // check if already calculated for n
        if (n in cache) {
            return cache[n];
        } else if (n < 2) { // base case
            return n;
        } else {
            // store result in cache
            cache[n] = fib(n - 1) + fib(n - 2);
            return cache[n];
        }
    }
}

Now you can see we’ve added some extra code but this solution greatly optimizes the previous one bringing the runtime down to O(n). So let’s go over what we’re doing here. First, we’re assigning a hash map to a variable called cache. This is a good name for it since what we’re doing is basically caching the result of our function calls. Then on line 4, we’re utilizing the concept of closure in Javascript by returning a function, this is so we don’t keep resetting our cache variable on each recursive call. We pass n into our nested function and on line 6 we check if we’ve already solved for n . We also include our base case on line 8. On lines 12 and 13 is where we perform the calculation, store the result, and return it.

To run this function we can store the function definition in a variable and call it with any number passed in as an argument.

const callFib = dynamicFibonacci();
callFib(10); // 55

This gives us our answer to the Fibonacci problem. Let’s further prove why this solution is optimal to our previous one by tracking the number of calculations with the numCalculations variable again.

numCalculations = 0; // reset to 0

function dynamicFibonacci() {
    let cache = {};

    return function fib(n) {
        // keep track of function calls
        numCalculations++;

        if (n in cache) {
            return cache[n];
        } else if (n < 2) { // base case
            return n;
        } else {
            cache[n] = fib(n - 1) + fib(n - 2);
            return cache[n];
        }
    }
}

Let’s go ahead and pass in the same number as we did with the previous solution so we can compare the two.

const callFib = dynamicFibonacci();
callFib(20); // 6765
console.log(numCalculations); // 39

Wow, we only get 39 calculations here. That’s a lot less compared to the 21891 calculations from the plain old recursive solution.

Identifying Dynamic Programming problems like Fibonacci

To identify problems where Dynamic Programming can be helpful we should ask ourselves several questions about the problem such as:

• Can the problem be divided down into sub-problems?

• Is recursion involved?

• Are the sub-problems overlapping?

This could be a good gauge for identifying problems that can be optimized with Dynamic Programming techniques like Memoization.

Summary

In this article, we went over how to optimize the Fibonacci sequence problem using Dynamic Programming. We utilized the technique of Memoization to get rid of all those extra calculations being made from recursive functions calls.

For our solution, we used what is considered a top-down approach which is about breaking down a larger problem into smaller ones. The opposite of this approach is a bottom-up approach which starts with the smaller simpler problems and works up to the larger more complex ones. We did not go over the bottom-up approach in this article but you can see a video of how it’s implemented for Fibonacci here.

Hopefully, this article has explained clearly how useful Dynamic Programming can be for optimizing our code so it doesn’t perform repetitive tasks and unnecessary work. Next time you’re solving a problem like the Fibonacci sequence, think about how you can optimize with a Dynamic Programming approach.