Register

C programming

1,596 views
6 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 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
Voting & Accepting an answer helps improve the community
← Previous · Virtual Address pagi...Next → · Test series
← Previous in category · For_LoopNext in category → · Programming
Position:
Show:

Related questions

9 9 votes
3 3 answers
442
442 views
GO Classes asked Jun 17
442 views
GO Classes DPP | GATE CS | C Programming | Pointer Recursion
What is the output of the following code?#include <stdio.h void update(int n, int *p) { if (n <= 0) return; *p = *p + n; update(n - 2, p); *p = *p + n; } int main() { int...
6 6 votes
2 2 answers
372
372 views
GO Classes asked Jun 17
372 views
GO Classes DPP | GATE CS | C Programming | Recursion
What is the output of the following code?#include <stdio.h int fun(int n) { int x = n; if (n <= 0) return 0; x = x + 2; return x + fun(n - 2); } int main() { printf("%d",...
6 6 votes
2 2 answers
414
414 views
GO Classes asked Jun 17
414 views
GO Classes DPP | GATE CS | C Programming | Call Count
How many times is $\texttt{fun()}$ called when the following code is executed? (Count the first call also).#include <stdio.h int fun(int n) { if (n <= 1) return 1; return...
6 6 votes
3 3 answers
381
381 views
GO Classes asked Jun 17
381 views
GO Classes DPP | GATE CS | C Programming | Return Trace
What is the output of the following code?#include <stdio.h int fun(int n) { if (n <= 1) return n + 1; if (n % 2 == 0) return fun(n - 1) + fun(n - 2); return fun(n - 2) + ...