CS3343/3341
 Analysis of Algorithms 
  Fibonacci Numbers   
   Using Memoization  

The Memoization Approach: The usual recursive function to calculate the nth Fibonacci number takes exponential time in terms of n. This is because it calculates smaller values over and over again.

If a program just saved answers to simpler problems and looked them up when needed, the calculation would be very fast. This process is called memoization and is illustrated in the program below:

  1. The function fs below calculates the the nth Fibonacci number in the normal recursive way, very inefficiently.
  2. The function f below calculates the the nth Fibonacci number using memoization. It keeps an array F, and when the program calculates the nth Fibonacci number it stores this value into F[n]. Before calculating f(n), the program first looks to see if the answer is already stored in F[n], and just returns that value if the answer is there.

The Fibonacci Program, Using Memoization
/* Program to calculate Fibonacci numbers.
 * Uses recursive formula, but saves answers in
 * an array.  Written by Neal R. Wagner
 */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MAXN 100 /* largest possible input */
long f(long); /* memoized calc. of nth Fibonacci # */
long fs(long); /* slow calc. of nth Fibonacci # */
void initF(void); /* initialize F to -1 values */
long F[MAXN]; /* array holding answers */
long recurs; /* number of recursive calls */
long ins;    /* number of table insertions */

int main() {
  long n;
  for( ; ; ) {
    recurs = 0;
    ins = 0;
    scanf("%ld", &n);
    if (n < 0) { printf("Bad input\n"); exit(1); }
    printf("No  array:  |%5ld  |%12ld  |", n, fs(n));
    printf("%12ld  |          |\n", recurs);
    recurs = 0;
    initF();
    printf("Use array:  |%5ld  |%12ld  |", n, f(n));
    printf("%12ld  |%8ld  |\n", recurs, ins);
  }
}


long f(long n) {
   long f1, f2;
   recurs++;
   if (n <= 1) return(n);
   if ( F[n] >= 0 ) {
       /* answer in F */
       return(F[n]);
   }
   f1 = f(n-1);
   F[n-1] = f1; ins++;
   f2 = f(n-2);
   F[n-2] = f2; ins++;
   F[n] = f1 + f2; ins++;
   return(f1 + f2);
}
long fs(long n) {
   long f1, f2;
   recurs++;
   if (n <= 1) return(n);
   f1 = fs(n-1);
   f2 = fs(n-2);
   return(f1 + f2);
}
void initF(void) {
   long i;
   for(i = 0; i < MAXN; i++)
         F[i] = -1;
}


Note: This output file was assembled from multiple input runs.
------------+-------+--------------+--------------+----------+--------
Array used  |    n  |        f(n)  |   recursive  | inserts  |  time
  or not    |       |              |       calls  |          |
------------+-------+--------------+--------------+----------+--------
------------+-------+--------------+--------------+----------+--------
No  array:  |    5  |           5  |          15  |          |
Use array:  |    5  |           5  |           9  |      12  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   10  |          55  |         177  |          |
Use array:  |   10  |          55  |          19  |      27  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   15  |         610  |        1973  |          |
Use array:  |   15  |         610  |          29  |      42  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   20  |        6765  |       21891  |          |
Use array:  |   20  |        6765  |          39  |      57  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   25  |       75025  |      242785  |          |
Use array:  |   25  |       75025  |          49  |      72  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   30  |      832040  |     2692537  |          |  3 sec
Use array:  |   30  |      832040  |          59  |      87  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   35  |     9227465  |    29860703  |          | 30 sec
Use array:  |   35  |     9227465  |          69  |     102  |
------------+-------+--------------+--------------+----------+--------
No  array:  |   40  |   102334155  |   331160281  |          |360 sec
Use array:  |   40  |   102334155  |          79  |     117  |
------------+-------+--------------+--------------+----------+--------

Revision date: 2012-09-30. (Please use ISO 8601, the International Standard Date and Time Notation.)