GATE CSE 2015 Set 3 | Question: 39

Question

Consider the following recursive C function.

void get(int n)
{
    if (n<1) return;
    get (n-1);
    get (n-3);
    printf("%d", n);
}

If $get(6)$ function is being called in $main()$ then how many times will the $get()$ function be invoked before returning to the $main()$?

• A. $15$
• B. $25$
• C. $35$
• D. $45$

Comments

Best explanation: https://www.geeksforgeeks.org/gate-gate-cs-2015-set-3-question-49/

---

How can  get(1) call to get(0) and get(-2) as n<1 ?.

---

T(n) = T(n-1) + T(n-3) +1
T(0) = 1 (counting get(0) as 1 count)
T(1) = 3
T(-1) = 1 (count get(-1) as 1 count)

solving T(6) in this will also give 25

Answer 1

Answer : Option B

$\text{T(n) = T(n-1) + T(n-3) + 2}$, here $\text{T(n)}$ denotes the number of times a recursive call is made for input $n$. $2$ denotes the two direct recursive calls.

$\text{T(n $\leq0$) = 0}$
$\text{T(1) = 2}$
$\text{T(2) = 4}$
$\text{T(3) = 6}$
$\text{T(4) = 10}$
$\text{T(5) = 16}$
$\text{T(6) = 24}$

So, answer is $\text{24 + 1}$ call from main = $25$.

Comments

For get(n) ..get(n-1) + get(n-2) calls +1 for itself get(n)

And if (n<=0) then no rec just one call

Isnt it right..in selected answer base condition is different hence it is +2

??

---

I didn't get how we're adding 2 to the reccurrence. A little bit of explanation would be helpful.

---

@Manu Shaurya Here T(n) is not the time complexity. It is the number of times a recursive call is made for input $n$. Now at first call, we call $2$ get functions. Thus the $2$ is added as the cost for each recursive call.

Answer 2

Total 25 function calls before returning to main() function.

Answer: B

Answer 3

@Arjun Sir I think we can also develop the recurrence like : 

 T(n) = T(n-1) + T(n-3) +1 ; otherwise
 T(n) = 1 ; for  n < 1 
   Which means if the node at which  we are standing is greater than equal to one then we will calculate the calls in (n-1) part + in        (n-3) part + 1 (since the node on which we are standing is also a call) and in case if n<1 then that will yields only 1.

T(1)=3 , T(2)= 3 + 1 + 1 = 5, T(3) = 5 + 1 + 1 = 7 , T(4) = 7 + 3 + 1= 11 , T(5) = 11 + 5 + 1 = 17,
T(6) = T(5) + T(3) + 1 =  17 + 7 + 1 = 25. 

Comments

function gets returned when n<1 not when n<=1.

---

@Nirmal Gaur 

void get(int n)
{
    if (n<1) return;
    get (n-1);
    get (n-3);
    printf("%d", n);
}

get(1):n=1 and if(1<1) return; $1<1$ is false so get(1) again called.

---

Yes Lakshman...that's what i was also saying, n gets returned when its value goes below 1 not when equals to 1.

Answer 4

Answer: B. 

Comments

Can u plzzz explain..plzz...!!