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:
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:
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)
.
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.
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: