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; }

- 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.
- What is the time complexity of the resulting program when computing $fib(n)?$

## 3 Answers

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.

### 24 Comments

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?

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?

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

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??

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??

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)**

### 1 comment

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.