+4 votes
140 views
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))

asked | 140 views
Do we need to save the function calls in a table after calculating or every function call is a fresh call ?
Every call is a fresh - there is no saving in the given code.
Yes, Sir right and also they have not mentioned anything :P

## 1 Answer

+7 votes
Best answer

$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,

answered by Veteran (46.4k points)
edited
Will add a art work later :)
Yes, Sure :)

+2 votes
3 answers
1
+1 vote
1 answer
2
+10 votes
7 answers
3