In Section 16.4 we talked about duplicate computation as one of the problems with recursion. Do we have this problem with the factorial and quicksort solutions presented in this chapter? The...

In Section 16.4 we talked about duplicate computation as one of the problems with

recursion. Do we have this problem with the factorial and quicksort solutions presented

in this chapter?

The Fibonacci function is defined as

fib(1) = 1,

fib(2) = 1,

fib(n) = fib(n − 1) + fib(n − 2) for n > 2.

We have written iterative versions of this function in Chapter 5 (see page 152). Write a

program to recursively compute fib(N). Your main program should request a positive

integer N from the user and output fib(N). If the user enters a negative number, prompt

her to try again.