GATE CSE 2000 | Question: 16

Question

A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array $f [ 0\ldots 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/statement 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)?$

Answer 1

Array $f$ is used to store the $fib()$ values calculated in order to save repeated calls. Since $n = 0$ and $n = 1$ are special cases we can store $fib(2)$ to $f[0], fib(3)$ to $f[1]$ and so on. The missing code completed would be:

if (f[n - 2] != 0){
    return f[n-2];
}
t = fib(n-1) + fib(n-2);
f[n-2] = t;
return t;

In this code, $fib(i)$ will do a recursion only once as once $fib(i)$ is calculated it is stored in array. So, the time complexity for $fib(n)$ would be $\Theta(n)$. 

PS: We can also store $fib(n)$ in $f(n)$, the above code just saves $2$ elements' space in the array. 

Comments

@Shaik Masthan

Can u explain a bit more. I am unable to get it

---

In a Recursive function call, we store the function call , inside another function call. But here we r storing it inside an array.

Where did you learn this from? A recursive call us any function calling itself -- it has nothing to do with storing. 

---

yes, that was wrong. But  after each function call, when we keeping those values inside an array, then is it still recursive call? No,  right?

That we have done here. Isnot it?

Answer 2

int fib(int n)

{

  if (n>m)

       printf('error');

  if(n==0)

       return 1;

  if(n==1)

      return 1;

  if (f[n]!=0)

      return (f[n-1]+f[n-2]);\\\ this is for reuse

  t=fib(n-1)+fib(n-2);

  f[n]=t ; \\ this for store the value

  return t;

}

In Array f[0...m] store all the value of  Fibonacci numbers 0 to m

time complexity is O(n)

Comments

for run upper code we use another function as main() shown in below

f=zeros(1,100);
for i=1:100
    f(i)=fib(i,f);
end

input_f

output_f

Answer 3

A.
(1) f[n]
(2) f[n];
(3) f[n] = t;

B. O(n)

Explanation: if(f[n]) { return f[n];} is executed when f[n] ≠ 0 
(because every non-zero value in C/C++ conditional statement is true). 
So it is meant to return the value of f[n] containing the desired value which was done 
in some previous call of fib(n) at the statement f[n] = t;

See my full code at http://ideone.com/SZRX0j.