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

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

---

For this pseudocode the recurrence equation for function calls is T(n) = 2T(n/2) + 2 ?

---

n	T(n) = T(n-1) + T(n-3) + 1
<1	=1
1	T(0) + T(-2) + 1 = 1+1+1 = 3
2	T(1) + T(-1) + 1 = 3+1+1 = 5
3	T(2) + T(0) + 1 = 5+1+1 = 7
4	T(3) + T(1) + 1 = 7+3+1 = 11
5	T(4) + T(2) + 1 = 11+5+1 = 17
6	T(5) + T(3) + 1 = 17+7+1 = 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

@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.

---

Sir T(n) is a invocation call so even T(-1),T(-2),T(0) is equal to 1 not 0 and recurrence relation will be

T(n)=T(n-1)+ T(n-3)+1(for current call like get(6))

---

@dakshvyas2025 If we assume T(n): no of function calls made for input n then T(n) = T(n -1) + T(n - 3) + 1, and T(<=0) = 1, then we get T(6) = 25 as answer, 

but in the Arjun sir's explanation it is assumed as T(n): no of recursive function calls made for input n. so we are adding the initional  function call for f(6) at the end.

Answer 2

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

Answer: B

Comments

My KInda Method

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. $25$

Comments

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

Answer 5

http://www.geeksforgeeks.org/gate-gate-cs-2015-set-3-question-49/

nicely explained

Comments

can u explain what they hav done ?? i am nt getting it ..