The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
781 views

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

  1. 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.
  2. What is the time complexity of the resulting program when computing $fib(n)$?
asked in Programming by Veteran (59.5k points)
edited by | 781 views

2 Answers

+24 votes
Best answer

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. 

answered by Veteran (355k points)
edited by
0
dont you think it should be f(n) instead of f(n-2) in the above code ?
+2
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.
+1
thanx
0
sir , i could not get question  :(
+2
We are using dynamic programming to reduce the time complexity of recursive solution to Fibonacci.
+1
o yeah... i could not think in this way...

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

thank you :)
0

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

0
@Abbas rt...
0
@papesh
What is Memoized Version in Dynamic Programming. how it differ from dynamic programming?
0
if f(n-2) is 0 that condition is not given

rt?
0
@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?
+1
0
Thank you
+2 votes

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)

answered by (45 points)
edited by
0

this code we are testiong on matlab

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

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,176 questions
45,681 answers
132,627 comments
49,580 users