Dynamic programming and Recurrence Equations

Note: this is not working on IE. Please use Firefox while I work out ignore the problems.

Tables and recursion

Take for instance the fibonacci series, defined by taking "old" values and creating from them "new" values. If the values are denoted f₀, f₁, ..., then we set,

Two methods immediately come to mind for this calculation. One is to keep a table f where f[i] gets filled in with value f_i. Very clever! This is called dynamic programming. The other method is to keep just the portion of the table that will be needed in the future, either discarding or printing out values of f_i outside (smaller i) this window. This second manner is the typical calculation of the i-th fibonacci number, as it seems wasteful (of storage, not time!) to keep around the j-th fibonacci number for all j less than i - only the previous two values are needed for future calculations, and in certain instances, we have not other future use of the other values. However, we will stay with the filling out the table variant.

The other method is straight recursion. This method will be very slow. Dynamic programming is involved in going from the slow recursive calculation to the fast table-based calculation.

USING DYNAMIC PROGRAMMING

f[1] = f[2] = 1
i = 3 
while (i<END_VALUE)
   f[i] = f[i-1] + f[i-2]
   i += 1
end_while

USING RECURSION

var g_count ;

function fib_recurse(i) {
   g_count = g_count + 1 ;
   if (i<3) return 1 ;
   else return fib_recurse(i-1) 
      + fib_recurse(i-2) ;
}

From recursion to tables

Why is the recursive version slow? Because evaluting F(i) will call F(i-2) twice. Since this is true, F(i-4) will be called at least four times (actually, it will be called 5 times), and F(i-6) at least 8 times (actually it will be called 13 times). If we look at F(1), it will be called an exponential number of times in the value i.

The table version avoids this by,

1. Solving each sub-problem only once, and placing the results in a table for future use.
2. Having the results in the table available for use when needed.

1. A recursive substructure the problem. Solving a problem of size i breaks down into solving the same problem over smaller sizes.
2. The recursion implemented in a straight-forward way would rediscover the same sub-problem over and over again. The branching structure makes that the sub-problem is revisted an exponential number of times.
3. The solution can be arranged so that when a sub-problem needs the result of another sub-problem, the sub-problem has already been solved, and the result can be found in a table, with out further recursion.

In our fibonacci series problem, it is obvious how to arrange the sub-problems. Order the collection of sub-problems that need to be solved in order to solve fib(i) in order of increasing i. Solve them in this order, so that when fib(i) needs the value of fib(i-2), it is already solved, and likewise for fib(i-1).

You can also let the computer figure out automatically the order of solutions, in some cases, by a process called memoization. For memoization, you fill in the table on-demand. First the table must be filled in with "unsolved" marks. For fibonacci, initialize the table to zeros. Then when the value of fib(i) needs to be consulted, look first in the table. If the table location has a value, it is the value of fib(i) and it should be used. If not, calculate fib(i) and place the result in the table for future reference.

USING DYNAMIC PROGRAMMING, MEMOIZATION

var g_fib_tab ;
var g_count ;

function fib_memo(i) {
    g_count = g_count + 1 ;
    if ( i<1 ) return 0 ; // error!
    if (g_fib_tab[i]!=undefined) return g_fib_tab[i] ;
    g_fib_tab[i] = fib_memo(i-1) + fib_memo(i-2) ;
    return g_fib_tab[i] ;
}

Timings

Note that the number of calls for the recursive version is almost exactly twice the output value of the fibonacci function. The number of calls for memoize is twice the value of the input to the fibonacci function.

Note that the size of problem that can be solved as been increasing even though I have not changed my machine or browser. It seems that Javascript has been getting very much faster.