edited by
4,694 views
26 votes
26 votes

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;
}
  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)?$
edited by

3 Answers

Best answer
40 votes
40 votes

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. 

edited by
4 votes
4 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)

edited by
2 votes
2 votes
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. 

Related questions

48 votes
48 votes
4 answers
3
Kathleen asked Sep 14, 2014
17,498 views
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the foll...