Analysis of Algorithms : An Active Learning Approach

9.3 DYNAMIC PROGRAMMING 253

if (N = 1) or (N = 2) then

return 1

else

return Fibonacci( N-1 ) + Fibonacci( N-2 )

end if

If we use this algorithm to find the sixth Fibonacci number, we would wind

up making the series of calls to this function represented in the tree in Fig. 9.6.

In examining this tree, you will see that Fibonacci(4) gets calculated twice

andFibonacci(3) gets calculated three times. For even larger Fibonacci

numbers, these values could be calculated even more times. For the tenth

Fibonacci number, the third would be calculated 21 times. We could improve

the efficiency of this algorithm if, instead of calculating from the top down, we

calculated from the bottom up. An alternative algorithm follows that uses an

array of previous values:

Fibonacci2( N )

N the Nth Fibonacci number should be returned

if (N = 1) or (N = 2) then

return 1

else

val[1] = 1

val[2] = 1

for i = 3 to N do

val[i] = val[i-1] + val[i-2]

end for

return val[N]

end if

Fibonacci(6)

Fibonacci(5) Fibonacci(4)

Fibonacci(3)Fibonacci(2)

Fibonacci(2)Fibonacci(1)

Fibonacci(3)

Fibonacci(3) Fibonacci(2) Fibonacci(2) Fibonacci(1) Fibonacci(2) Fibonacci(1)

Fibonacci(4)

■FIGURE 9.6
The calling
sequence for
Fibonacci(6)