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

dont you think it should be f(n) instead of f(n-2) in the above code ?

---

depends on how we store in array f[]. I already mentioned that fib[i] will be stored at f[i-2] as we don't store fib(0) and fib(1) in array- their checks are done at the beginning of the given code, so no point in storing them in array.

---

thanx

---

sir , i could not get question  :(

---

We are using dynamic programming to reduce the time complexity of recursive solution to Fibonacci.

---

o yeah... i could not think in this way...

values store in table and  then reuse ... got it !

thank you :)

---

That we say as Memoized Version in Dynamic Programming. Am I correct Arjun Sir??

---

@Abbas rt...

---

@papesh
What is Memoized Version in Dynamic Programming. how it differ from dynamic programming?

---

if f(n-2) is 0 that condition is not given

rt?

---

@Arjun sir,

Lets us say i calculated f(3) and f(2) and store in table.

Now f(4) is called,it needs f(3) and f(2), it will look into table for f(4) but will not find that.So,it will again call f(3) and f(2),which are already calculated(although that calls to  f(3) and f(2) will return in constant time ,but does this effect time complexity?

---

Thank you

---

Below is a snapshot of how this works

Consider my f[] array is as below

What this code does is, it does not store value for fib(0) and fib(1), rather it stores values of fib(n) for $n \geq2$

in f[n-2].

So, for Fib(2), the value is stored in f[0], for Fib(3), the value is stored in f[1] and so so...

Consider I have invoked Fib(10)

Below is the execution sequence

Now, it looks like the time complexity for this program will be $2^n$, but it's not.

When, the recursion will bottom out and start to trace back, it will use the values from the table for the repeated function calls involved.

Like at last, for Fib(2), it calls Fib(1)+Fib(0) and it gets resolved without further recursion and value returned is 2 and it is stored in f[0].

Now, when recursion goes back

for fib(3)=fib(2)(return value 2)+fib(1)(gives 1)=3 and stored in f[1]=3 and 3 returned to the caller fib(4).

Then  we go back

fib(4)=fib(3)(return value 3)+fib(2) (Now this fib(2) will use value from the table f[2-2]=f[0]=2)=3+2=5 stored in f[4-2]=f[2]=5.

And it goes on untill it finally evaluated fib(10).

So, number of function calls made for fib(10)=19

So, for fib(n) number of function calls would be $2n-1$

So, time complexity $\theta(n)$

Code : https://ideone.com/HciGrW

---

@Arjun Sir

If we write the code like this, will it be correct?

(1)if(n>=2)

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

    return t;

I mean even without putting some code in blank (2) and (3) also code can execute.

right?

---

mam, then how you are storing the result in to the given array.

if you doesn't save in the array, then every time you have calculate fib(2) and fib(3) etc.

 

So, basically 2nd blank is :- reuse the value which is stored in the array

3rd blank is :- store the value if you calculate it on first time.

---

@Shaik Masthan

without array, can we not do it?

---

mam, you can do it !

but in this question, you have to do it like this only !

there are so many algorithms for a problem, you have to choose one according to your question.

i mean to say, there is a way, without using recursion also i can write a program for fibonacci, but i can't do that for this question

---

@Shaik Masthan

U mean it stores inside t. So, it is done without recursion

right??

Even we can do it like this

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

This will consume 2 extra space in array, but we will get  total fibonacci series inside the f[ ] array  in this program

And no error in this code too. Right??

---

U mean it stores inside t. So, it is done without recursion

right??

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

this line causing recursion in the question... due to saving and reusing, we decreasing the time complexity

 

rest of your comment is right !

---

@Shaik Masthan

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

when we storing inside an array, it reduces the function call. right??

I mean this

when we do like this

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

that means one function call  is calling other function.

But, here is an array, having static storage. 

f[n]= fib(n - 1) + fib(n - 2);

So, can we say still be a recursive call??

---

can we say still be a recursive call??

yes

---

@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.