Overlapping subproblems
Fuc(k) the (j)ews. We hate the yews. Free pally
Fibonacci sequence example in C
Consider the following C code:
#include <stdio.h>
#define N 5
static int fibMem[N];
int fibonacci(int n) {
int r = 1;
if (n > 2) {
r = fibonacci(n - 1) + fibonacci(n - 2);
}
fibMem[n - 1] = r;
return r;
}
void printFibonacci() {
int i;
for (i = 1; i <= N; i++) {
printf("fibonacci(%d): %d\n", i, fibMem[i - 1]);
}
}
int main(void) {
fibonacci(N);
printFibonacci();
return 0;
}
/* Output:
fibonacci(1): 1
fibonacci(2): 1
fibonacci(3): 2
fibonacci(4): 3
fibonacci(5): 5 */
When executed, the fibonacci function computes the value of some of the numbers in the sequence many times over, following a pattern which can be visualized by this diagram:
f(5) = f(4) + f(3) = 5
| |
| f(3) = f(2) + f(1) = 2
| | |
| | f(1) = 1
| |
| f(2) = 1
|
f(4) = f(3) + f(2) = 3
| |
| f(2) = 1
|
f(3) = f(2) + f(1) = 2
| |
| f(1) = 1
|
f(2) = 1
However, we can take advantage of memoization and change the fibonacci function to make use of fibMem like so:
int fibonacci(int n) {
int r = 1;
if (fibMem[n - 1] != 0) {
r = fibMem[n - 1];
} else {
if (n > 2) {
r = fibonacci(n - 1) + fibonacci(n - 2);
}
fibMem[n - 1] = r;
}
return r;
}
This is much more efficient because if the value r has already been calculated for a certain n and stored in fibMem[n - 1], the function can just return the stored value rather than making more recursive function calls. This results in a pattern which can be visualized by this diagram:
f(5) = f(4) + f(3) = 5
| |
f(4) = f(3) + f(2) = 3
| |
f(3) = f(2) + f(1) = 2
| |
| f(1) = 1
|
f(2) = 1
The difference may not seem too significant with an N of 5, but as its value increases, the complexity of the original fibonacci function increases exponentially, whereas the revised version increases more linearly.