GATE 2015 CS (CS3) – Question 38
How many calls to get, including the initial and base-case calls, occur for get(6)?
void get(int n) {
if(n<1) return;
get(n-1);
get(n-3);
printf("%d",n);
}Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 25
Explanation
Let C(n)=1 for n<1. Otherwise C(n)=1+C(n−1)+C(n−3), counting the current invocation. Values C(1) through C(6) are 3,5,7,11,17,25. Thus the total is twenty-five, B, including invocations that immediately return.