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

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?

---

The array indexing can be from n rather than n-2 right? Since using f[n-2] is a more optimized version of f[n] as n=0 and n=1 return from the if statments and never reach the part of code where they are stored in the array and the array entries will go to waste for n=0,1.

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. 

Comments

I was thinking only why are we storing the n-2 value 😅 when we can store the n value like yours.

thanks buddy :)

Answer 4

1. Its a simple algorithm design for Fibonacci using Dynamic Programming

Missing Code:

 if (f[n] != 0){ 

 return f[n];

 } 

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

f[n] = t; 

return t;

2. Unique calls in Fibonacci will be n, so time complexity will be O(n).

 

 

 

 

 

 

 

Comments

You made part a, so easy to understand

Answer 5

Since the base cases n=0 and n=1 are already handled by the early if statements, the function only reaches the lower array logic when n >= 2. By using f[n-2], we map the values efficiently without wasting the first two array slots. As the array f[] is explicitly given in the question, our goal is to use it to store and reuse calculated values, which is the exact definition of Memoization (a Top-Down Dynamic Programming approach). This simple array check completely reduces the execution time from a slow exponential (O(2^n)) down to an optimal linear (Theta(n))