Page 387 - Discrete Mathematics and Its Applications

366 5 / Induction and Recursion

f 4

f 3
f 2

f 2 f 1 f 1 f 0

f 1 f 0

FIGURE 1 Evaluating f 4 Recursively.

tree consists of a root labeled with f 4 , and branches from the root to vertices labeled with the
two Fibonacci numbers f 3 and f 2 that occur in the reduction of the computation of f 4 . Each
subsequent reduction produces two branches in the tree. This branching ends when f 0 and f 1
are reached. The reader can verify that this algorithm requires f n+1 − 1 additions to find f n .
Now consider the amount of computation required to find f n using the iterative approach
in Algorithm 8.

ALGORITHM 8 An Iterative Algorithm for Computing Fibonacci Numbers.

procedure iterative fibonacci(n: nonnegative integer)
if n = 0 then return 0
else
x := 0
y := 1
for i := 1to n − 1
z := x + y
x := y
y := z
return y
{output is the nth Fibonacci number}

This procedure initializes x as f 0 = 0 and y as f 1 = 1. When the loop is traversed, the sum of x
and y is assigned to the auxiliary variable z. Then x is assigned the value of y and y is assigned
the value of the auxiliary variable z. Therefore, after going through the loop the first time, it
follows that x equals f 1 and y equals f 0 + f 1 = f 2 . Furthermore, after going through the loop
n − 1 times, x equals f n−1 and y equals f n (the reader should verify this statement). Only n − 1
additions have been used to find f n with this iterative approach when n> 1. Consequently, this
algorithm requires far less computation than does the recursive algorithm.
We have shown that a recursive algorithm may require far more computation than an iterative
one when a recursively defined function is evaluated. It is sometimes preferable to use a recursive
procedure even if it is less efficient than the iterative procedure. In particular, this is true when
the recursive approach is easily implemented and the iterative approach is not. (Also, machines
designed to handle recursion may be available that eliminate the advantage of using iteration.)