Section 3.1 Recursive Definitions
173
27. Write a pseudocode recursive algorithm for a function to compute F(n), the nth Fibonacci number.
28. Walk through your recursive algorithm from Exercise 27 to compute F(6).
a. How many times is the function invoked?
b. How many times is F(4) computed?
c. How many times is F(3) computed?
d. How many times is F(2) computed?
Exercises 29 and 30 concern a proof of correctness of the following iterative algorithm for a function to compute
F(n), the nth Fibonacci number.
F(positive integer n)
//function that iteratively computes the value of
//the nth Fibonacci number
Local variables:
positive integer i
//loop index
positive integers p, q, r
//terms in Fibonacci sequence
if n = 1 then
return 1
else
if n = 2 then
return 1
else
i = 2
p = 1
//p = lagging term in Fibonacci sequence
q = 1
//q = leading term in Fibonacci sequence
while i < n do
r = p + q
//form the next term as the
//sum of the two previous terms
p = q
//bump up p
q = r
//bump up q
i = i + 1
end while
//q now has the value F(n)
return q
end if
end if
end function F
29. a. In the iterative Fibonacci algorithm, the condition B for loop continuation is i < n, so B′ is i ≥ n, but
what is the exact value of i when the loop terminates?
b. When the loop exits, you want q = F(n); what do you want for the value of p at that point?
30. a. Write the loop invariant Q for the iterative Fibonacci algorithm.
b. Prove that Q is a loop invariant.