now clear thank you sir ! :)

The Gateway to Computer Science Excellence

+18 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___________.

+40 votes

Best answer

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 $fib(0)$ and $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$

+9

@Arjun sir,

why have you taken fib(0) and fib(1) as 0,although there are no recursive calls,but there will be one call fib(0) for 0 and fib(1) for 1,the initial function call which should be included.

I think it should be:-

T(n)= T(n-1)+T(n-2) +1 // the 1 is initial function call.

T(0)=T(1)=1, as base condition ,although answer reamins same.

Please check once

why have you taken fib(0) and fib(1) as 0,although there are no recursive calls,but there will be one call fib(0) for 0 and fib(1) for 1,the initial function call which should be included.

I think it should be:-

T(n)= T(n-1)+T(n-2) +1 // the 1 is initial function call.

T(0)=T(1)=1, as base condition ,although answer reamins same.

Please check once

0

**Is this Recurrence Relation Correct? Coz, for n=2, it will give T(2) = T(1) + T(0) + 1 $\Rightarrow$ T(2) = 1 (coz T(0) and T(1) = 1).**

0

I don't think that's correct. Correct one is:

$T(n)=T(n-1)+T(n-2)+1$; $n>1$

$T(0) = T(1) = 1$

So,

$T(2) =3$

$T(3) =5$

$T(4) =9$

$T(5) =15$

$T(6) =25$

$T(7) =41$

+1

@Arjun Sir,

In the recurrence relation $T(n),$ you have already added 1 which is for the initial call. So, $T(n)$ defined by you is " the number of times fib is called (including the first call) for evaluation of fib(n), n>1".

Hence, all the $T(i) $ values should be 1 more than what they are and there is no need for the last line in the answer.

+33 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

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

+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$

52,345 questions

60,513 answers

201,930 comments

95,355 users