retagged by
10,066 views
32 votes
32 votes

Consider the following recursive definition of $fib$:

 fib(n) :=  if n = 0 then 1
            else if n = 1 then 1
            else fib(n-1) + fib(n-2)

The number of times $fib$  is called (including the first call) for evaluation of $fib(7)$ is___________.

retagged by

8 Answers

Best answer
59 votes
59 votes

The recurrence relation for the number of calls is $$T(n) = T(n-1) + T(n-2) + 1$$ where $1$ is for the current called function.

  • $T(0) =T(1) = 1$ (for $\textsf{fib}(0)$ and $\textsf{fib}(1)$, there are no recursive calls and only current function call is there).
  • $T(2) = 3$
  • $T(3) = 5$
  • $T(4) = 9$
  • $T(5) = 15$
  • $T(6) = 25$
  • $T(7) = 41$

Answer: $41$


We can also calculate the number of calls excluding the current function call or the number of recursive calls initiated by a given function as follows:

$$T(n) = T(n-1) + T(n-2) + 2$$ $(2$ recursive calls one each for $T(n-1)$ and $T(n-2))$

  • $T(0) = T(1) = 0$ (no recursive calls happen here)
  • $T(2) = 2$
  • $T(3) = 4$
  • $T(4) = 8$
  • $T(5) = 14$
  • $T(6) = 24$
  • $T(7) = 40$

Now, we can add the initial call for $\textsf{fib}(7)$ and get answer as $40+1 = 41.$

edited by
35 votes
35 votes
fib(0)=1 (because fib(0) is also a function call)

fib(1)=1 (because fib(1) is also a function call)

fib(2)= fib(0) + fib(1) +1= 3 ( 1 is added because fib(2) is also included in function call)

fib(3)= fib(2)+fib(1)+1= 5

fib(4)= fib(2)+fib(3)+1 = 9

fib(5)= fib(4)+fib(3)+1 = 15

fib(6)= fib(5)+fib(4)+1 = 25

fib(7)= fib(5)+fib(6)+1 = 41

HENCE 41 CALLS
edited by
7 votes
7 votes

Answer: 41.

Correct recurrence relation is  -->

f(n) = 1 + f(n - 1) + f(n - 2).

For more details please refer https://stackoverflow.com/questions/1738923/number-of-calls-for-nth-fibonacci-number

Although f(7) is small value. So value could be obtained via direct substitution.

But if value is large then non - homogenous recurrence relation solution could be used.

$f(n) = \frac{1}{2^{(n+1)} * \sqrt{5}} * ( (1- \sqrt{5})^{n+1}- (1+ \sqrt{5})^{n+1} ) + 2$

edited by
Answer:

Related questions

44 votes
44 votes
2 answers
1
Kathleen asked Sep 12, 2014
13,566 views
The weighted external path length of the binary tree in figure is ______
50 votes
50 votes
3 answers
2
Kathleen asked Sep 12, 2014
8,636 views
The minimum number of comparisons required to sort $5$ elements is ______
25 votes
25 votes
5 answers
3
Kathleen asked Sep 12, 2014
8,135 views
Consider the number given by the decimal expression:$$16^3*9 + 16^2*7 + 16*5+3$$The number of $1’s$ in the unsigned binary representation of the number is ______
24 votes
24 votes
3 answers
4
Kathleen asked Sep 12, 2014
4,358 views
Consider the following PASCAL program segment:if i mod 2 = 0 then while i >= 0 do begin i := i div 2; if i mod 2 < 0 then i := i - 1; else i := i – 2; end;An appropria...