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.

/* 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>
#define MAXN 100 /* largest possible input */
long f(long); /* memoized calculation of nth Fibonacci # */
long fs(long); /* slow calculation 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 */

main() {
    long n;
    for( ; ; ) {
       recurs = 0;
       ins = 0;
       scanf("%ld", &n);
       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 already 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;
}

------------+-------+--------------+--------------+----------+--------
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  |
------------+-------+--------------+--------------+----------+--------