JHAVÉ Java-Hosted Algorithm Visualization Environment |

Home | Learners | Instructors | Developers | Download |

The objectives of this laboratory are

- to illustsrate the basics of dynamic programming; that is, using an array to replace of recursive calls which may occur numerous time
- to demonstrate the run-time efficiency improvement of the dynamic programming solution over the recursive solution, and

To prepare for this lab activity, read the algorithm description and compare it with your textbook, if available.

Given a pair of base values f_{0} and f_{1} to initiate the computation, the k'th fibonacci
number can be computed by

This gives immediate rise to the recursive formulation to compute fibon(n):

fibon(n) = fibon(n-1) + fibon(n-2) if n >= 2 fibon(0) = 1 fibon(1) = 1

An iterative solution is also immediately apparent and in the classic sense a prototypical, albeit straight-forward, solution to a dynamic programming problem.

fibon[0] = 1; fibon[1] = 1; for (int j = 2; j <= n; j++) fibon[j] = fibon[j-1] + fibon[j-2];

In our visualization the recursive call tree for some modest value of n is produced. In the call tree, a number of calls are repeated - recursion does not "remember" values it has previously computed. An array whose dimension depends upon the number of parameters of the problem (in this case just one - the fibonacci number n) can be used to serve as a memory for the recursion OR more typically in dynamic programming problems lead directly to a solution which includes an array - as demonstrated above. As an intermediate step, the program that follows uses recursion to find fibonacci numbers but adds "memory" so that once a value is computed it never leads to a recursive call.

// to compute fibon(n) int[] d = new int[n+1]; for (int j = 2; j<=n; j++) d[j] = -1; d[0] = 1; d[1] = 1; int fibon(int n) { if (d[n-1] < 0) d[n-1] = fibon(n-1); return (d[n-1]+d[n-2]); }

There are only 4 recursive calls made exactly the number of iterations of the loop for the iterative approach. The implementation utilizes tail recursion to perform its "looping".

The most dramatic impact of the visualization is, for small n, the sheer size (a nearly complete binary tree) of the recursive call tree compared to the 1-dimensional matrix that is needed for the dynamic programming solution. As the dynamic programming matrix is filled, for position k the solution requires that the sum of the entries at the indices k-1 and k-2 be calculated - the two cells whose values are added are shown in mint green each step of the execution. At the same time, in the recursive call tree, each of the calls made to f(k-1) and f(k-2) are shown by coloring those nodes mint green. This provides an illustration of the savings of the dynamic programming approach.

Before executing the visualization the user is allowed to decide whether they want to alter the base case for computing the fibonacci number. This is done through a dialog window.

You can also explore the algorithm's dynamic behavior using the algorithm
visualization environment *JHAVÉ*. If you have not worked with *JHAVÉ* before,
please take the time to instructions on using *JHAVÉ* first.

- Choose different base case values.
- Choose different values for n - but keep them reasonably small.