The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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___________.

asked in Programming by Veteran (69k points)
recategorized by | 640 views

5 Answers

+25 votes
Best answer
The recurrence relation for the no. of calls is $$T(n) = T(n-1) + T(n-2) + 2$$

$T(0) =T(1) = 0$ (for $fib(0)$ and $fib(1)$, there are no recursive calls).

$T(2) = 2$

$T(3) = 4$

$T(4) = 8$

$T(5) = 14$

$T(6) = 24$

$T(7) = 40$.

Counting the initial call we get $40 + 1 = 41$.
answered by Veteran (347k points)
edited by
ok...just confuse between value and call ...

now clear thank you sir ! :)
sir why this extra 2 is include ???

because it have been called twice before
sir why we are adding 1, can you please explain.
@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
clear now
+9 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

answered by Veteran (14.7k points)
edited by
+3 votes
Answer: 41

Make the recursion tree.
answered by Veteran (36.4k points)
+3 votes

Answer: 41.

Correct recurrence relation is  -->

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

For more details please refer

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$

answered by Veteran (14.7k points)
edited by
+2 votes
Formula for no.of calls in f(n) =2f(n)-1 when f(0)=1

only applied  fibonacci series

where f(0)=1


f(2)=2  i,e (f(0)+f(1))


so no.of calls 2(21)-1=41

remember when f(0)=0,f(1)=1 then formula changes as 2f(n+1)-1
answered by Junior (679 points)
how no of call is 2f(n)-1 ??

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

34,170 questions
40,846 answers
39,703 users