in Programming in C retagged by
10,011 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___________.

in Programming in C retagged by
10.0k views

8 Answers

59 votes
59 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 $\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
by

4 Comments

@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.

1
1
Yes, thanks for pointing out. Fixed now.
1
1
These recurrence relations are valid for $n>=2$
0
0
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

2 Comments

thank you solving i'm also also solving on this way.
0
0
nice sushmita mam
0
0
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

2 Comments

I think this recurrence relation is correct.

Selected answer is not considering (first function call)
0
0
U went too far ahead than required :)
0
0
5 votes
5 votes
Answer: 41

Make the recursion tree.
Answer:

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