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

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

1 comment

how no of call is 2f(n)-1 ??
2
2
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 vote
1 vote

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

0 votes
0 votes
total 41 calls
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