816 views
6 votes
6 votes
int func(int n) {
    if(n<3)
    return 1;
    else 
    return func(n-1)+func(n-3)+1;
}

How many invocations for calculating func(func(5))

2 Answers

Best answer
9 votes
9 votes

$F(5) = F(4) + F(2) + 1$

$F(4) = F(3) + F(1) + 1$

$F(3) = F(2) + F(0) + 1$ 

Hence, Solving all gives $F(5) = 7$ with $3$ distinct invocations.


$F(7) = F(6) + F(4) + 1$

$F(6) = F(5) + F(3) + 1$

$F(5) = F(4) + F(2) + 1$

$F(4) = F(3) + F(1) + 1$

$F(3) = F(2) + F(0) + 1$

And, Solving all gives $F(7) = 17$ with $8$ invocations, assuming there is no saving in the above code.

Or,

edited by

Related questions

3 votes
3 votes
3 answers
1
Laxman Ghanchi asked May 19, 2023
1,111 views
#include<stdio.h void print(int n) { printf("Hello "); if(n++ == 0) return ; print(n); n++; } int main() { void print(); print(-4); }How many times printf execute?? And H...
0 votes
0 votes
1 answer
2
Laxman Ghanchi asked May 19, 2023
657 views
#include<stdio.h>void print(int n){ printf("Hello "); if(n++ == 0) return ; print(n); n++;}int main(){ void print(); print(-4);}
0 votes
0 votes
1 answer
3
0 votes
0 votes
0 answers
4
abhinowKatore asked Dec 5, 2022
599 views
What will be the return value of the below function, if it is called a sample(4)? int sample(int x){ if( x == 0 || x ==2) return 1; return (sample( x) * (x ));}