Dynamic Programming
Optimizing recursion using dynamic programming
Note: This article takes a look at a technique that makes recursion much faster. See the recursion article for more context.
Let’s review the Fibonacci sequence. The first two numbers are 0 and 1, and every number after that is the sum of the previous two numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Take a minute to look at this sequence. Say you needed to find a specific value in this sequence - the 89th, for example. How would you use recursion to find that value? Remember a recursive function is a function that calls itself to break down major problems into smaller subproblems, then breaks those subproblems into even smaller subproblems. What would the base case for this recursive function be? The recursive case?
As mentioned above, the first two numbers of this sequence are 0 and 1. This is the base case. Every other number is the sum of the previous two numbers, which can eventually be broken down into the first and second Fibonacci numbers using the recursive case. This code calculates the
n
th Fibonacci number:
Code:
def fib(n):
    # base case 1
    if n == 1:
        return 0
        
    # base case 2
    if n == 2:
        return 1
    
    # recursive case
    return fib(n - 1) + fib(n - 2)
    
    
# Unit tests to make sure our code is working
print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))
print(fib(7))
print(fib(8))
Output:
> 0
> 1
> 1
> 2
> 3
> 5
> 8
> 13
Code:
public class FibonacciNumbers {
    public static void main(String[] args) {
        // Unit tests to make sure our code is working
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(5));
        System.out.println(fib(6));
        System.out.println(fib(7));
        System.out.println(fib(8));
    }
     
    static int fib(int n) {
        // base case 1
        if(n == 1) {
            return 0;
        }
        
        // base case 2
        if(n == 2) {
            return 1;
        }
        
        // recursive case
        return fib(n - 1) + fib(n - 2);
    }
}
Output:
> 0
> 1
> 1
> 2
> 3
> 5
> 8
> 13
Code:
#include <iostream>

using namespace std;

int fib(int n) {
    // base case 1
    if(n == 1) {
        return 0;
    }
    
    // base case 2
    if(n == 2) {
        return 1;
    }
    
    // recursive case
    return fib(n - 1) + fib(n - 2);
}

int main() {
    // Unit tests to make sure our code is working
    cout << fib(1) << "\n";
    cout << fib(2) << "\n";
    cout << fib(3) << "\n";
    cout << fib(4) << "\n";
    cout << fib(5) << "\n";
    cout << fib(6) << "\n";
    cout << fib(7) << "\n";
    cout << fib(8) << "\n";

    return 0;
}
Output:
> 0
> 1
> 1
> 2
> 3
> 5
> 8
> 13
Notice that when you call
fib(n)
, the function needs to find the values of
fib(n-1)
and
fib(n-2)
. Solving for these smaller fibonacci numbers are subproblems — they are smaller problems that need to be solved in order to solve the whole problem.
Here is the issue: if you want to calculate a very large Fibonacci number (for example, the 100th Fibonacci number) it takes ages. Look at how calculating
fib(6)
runs:
dynamic-programming-img-1.png
As you can see, just calling this function for a number as small as 6 takes 15 calculations. It gets ugly very quickly with higher numbers. But take a closer look. Are there some calls to
fib()
that are identical?
fib(4)
is called twice, and each time it calls
fib(3)
and
fib(2)
. Then, each
fib(3)
calls
fib(2)
and
fib(1)
. That’s a lot of repetitive calls! It would be easier to just call
fib(4)
once, and then save that number to use later because it never changes.
You wouldn’t have to re-evaluate that subproblem again for that Fibonacci number no matter how many times it comes up!
This technique of storing the solutions to subproblems that are repeatedly solved is called dynamic programming. Dynamic programming is a powerful technique that has applications for a wide variety of problems. For instance, think of a shortest path algorithm— what is the best way to get from A to B? Well, if it is possible to find the best way to just get from A to some point in between, we can treat it as a sub-problem to evaluate, turning this daunting problem into smaller steps.
There are two requirements that need to be fulfilled in order to apply dynamic programming to a problem:
  • Overlapping subproblems - there are (1) subproblems and (2) the solutions to some (or all) of the subproblems need to be used more than once
  • Optimal substructure - the larger problem can be broken down into subproblems.
Let’s modify the
fib()
function to apply dynamic programming in 3 steps:
  1. Create an array called
    dp
    to store the solutions to our subproblems when we calculate them. In this array,
    dp[x]
    is equivalent to the output of
    fib(x)
    .
  2. Add another base case that checks if we’ve already solved a subproblem and return the previously-calculated solution if we’ve already solved it.
  3. Add code to the recursive case that stores solved subproblems into
    dp
    .
Code:
dp = [0] * 10000

def fib(n):
    # base case - subproblem we’ve already solved
    if dp[n] != 0:
        return dp[n]
    
    # base case - fib(1)
    if n == 1:
        return 0
        
    # base case - fib(2)
    if n == 2:
        return 1
    
    # recursive case
    dp[n] = fib(n - 1) + fib(n - 2)
    return dp[n]
    
    
# Unit tests to make sure our code is working
print(fib(1))
print(fib(2))
print(fib(3))
print(fib(40))
Output:
> 0
> 1
> 1
> 63245986
Code:
public class FibonacciNumbers {
    public static void main(String[] args) {
        // Unit tests to make sure our code is working
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(40));
    }
    static int[] dp = new int[10000];
    static int fib(int n) {
        // base case - subproblem we’ve already solved
        if(dp[n] != 0) {
            return dp[n];
        }
        
        // base case - fib(1)
        if(n == 1) {
            return 0;
        }
        
        // base case - fib(2)
        if(n == 2) {
            return 1;
        }
        
        // recursive case
        dp[n] = fib(n - 1) + fib(n - 2);
        return dp[n];
    }
}
Output:
> 0
> 1
> 1
> 63245986
Code:
#include <iostream>

using namespace std;

int dp[10000] = {};

int fib(int n) {
    // base case - subproblem we’ve already solved
    if(dp[n] != 0) {
        return dp[n];
    }
    
    // base case - fib(1)
    if(n == 1) {
        return 0;
    }
    
    // base case - fib(2)
    if(n == 2) {
        return 1;
    }
    
    // recursive case
    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

int main() {
    // Unit tests to make sure our code is working
    cout << fib(1) << "\n";
    cout << fib(2) << "\n";
    cout << fib(3) << "\n";
    cout << fib(40) << "\n";

    return 0;
}
Output:
> 0
> 1
> 1
> 63245986
Dynamic programming is a powerful optimization technique that can greatly reduce recursion runtimes. While we’ve only seen one example with fibonacci numbers in this article, there are many other applications for dynamic programming and we encourage everyone to continue learning about it (e.g., Dijkstra's algorithm, Tower of Hanoi, egg drop puzzle, matrix multiplication)!
You can play with all the code we've used in this article on Replit:
Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!
Copyright ©2021 Howard County Hour of Code