A recursive program to compute Fibonacci numbers is shown below. Assume you…
PYQ GATE 2000
A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array f[0…..m] with all elements initialized to 0.
fib(n) {
if (n > M) error();
if (n == 0) return 1;
if (n == 1) return 1;
if ( ) _________(1)
return _________(2)
t = fib(n − 1) + fib(n − 2);
_________(3)
return t;
}(a) Fill in the boxes with expressions/statements to make fib() store and reuse computed Fibonacci values. Write the box number and the corresponding contents in your answer book.
(b) What is the time complexity of the resulting program when computing fib(n)?
Sign up free to check your answer
Sign up freeLoading lesson…

