retagged by
10,063 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

4 votes
4 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(1)=1

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

f(3)=3............f(7)=21

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

remember when f(0)=0,f(1)=1 then formula changes as 2f(n+1)-1
3 votes
3 votes
#include <stdio.h>
int fib(int n);
int count =0 ;
int main()
{
  fib(7);
  printf("%d" , count);
  return 0;
}

int fib(int n)
{   count++;
    if (n==0) return 1;
    else if (n==1) return 1;
    else return (fib(n-1) + fib(n-2));
    
}
1 votes
1 votes

For those who are having difficulty visualising the 41 functions calls for fib(7), I have drawn the recursion tree.

Answer:

Related questions

44 votes
44 votes
2 answers
1
Kathleen asked Sep 12, 2014
13,563 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,134 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,357 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...