Fibonacci Numbers -- Chuck Leska (Draft)

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.

The Fibonacci Number Computation

Given a pair of base values f₀ and f₁ to initiate the computation, the k'th fibonacci number can be computed by

f_k = f_k-1 + f_k-2 for k >= 2.
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".

Dynamic Programming

The fundamental idea behind dynamic programming is to solve a given problem by solving a series of subproblems. The series of subproblems is conceived in a manner that permits a subsequent subproblem to be solved by combining the solutions of one or more of the subproblems already solved - making dynamic programming a bottom-up approach. The intermediate solutions are held in an array to eliminate repeating work. For optimization problems a dynamic programming algorithm is typically developed in three steps. The first step establishes a recursive formulation that yields the optimal solution to an instance of the problem; the next step computes the the value of a an optimal solution in a bottom-up fashion; and, the final step constructs an optimal solution in a bottom-up fashion.

The Visualizaton

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.

Exercises

I. Explore the Fibonacci numbers within JHAVÉ

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 input options and step through the algorithm. Answer the questions as they appear to predict the next step.

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