The Gateway to Computer Science Excellence
+40 votes
4.4k views

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()$?

  1. $15$
  2. $25$
  3. $35$
  4. $45$
in Algorithms by Veteran (105k points)
edited by | 4.4k views
+5
+1
How can  get(1) call to get(0) and get(-2) as n<1 ?.
0
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

4 Answers

+54 votes
Best answer

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

by Veteran (424k points)
edited by
+2
Sir why +2 in the recurrence relation ???
+10

The recurrence is for counting the number of function calls. For a function call, we have 2 direct recursive calls:

 get (n-1);
 get (n-3);

So, 2 is in the recurrence for this. 

+4
I thought +2 was for the if( condition ) return ;  and printf() ;

But, it's wrong .

your explanation cleared it . thanks
0
Sir , in general whenever we form a recurrence relation it is always related to number of recursive calls made and the amount of work done in the function so then why 2 ,why not T(n)=T(n-1)+T(n-3)+const ,I am not getting it .
0
Here 2 works as constant
0

Sir,  how come T(1)=2

                          T(2)=4

                          T(3)=6......??

I m not getting it... someone plz explain/...

0
for better visualization of @Arjun sir answer, you can draw a tree for g(6) just break in three part. and you can easily count how many function evovekd, which will give same result.
0
@Rohit

for n=6... it will be (5) , (3), (print)....................total call -3

for 5....it will be (4),(2),  (print)....................total call -3

so on...ryt..??

total  24 calls will be made  + from main.......ryt.??
0
@prateek kumar can u show  the tree for get(6) .  i made the tree in it i devide three part one for get(n-1) second for n-3 and third for printf()  then in counting printf() is also counted then i got 25 is it correct?? but why we counting printf(); can u tell me
0

@Arjun SIR , Why did u take 2 ?  I didn't get that logic 

You said 

The recurrence is for counting the number of function calls. For a function call, we have 2 direct recursive calls:

These two direct recursive calls are represented as 

T(n-1) + T(n-3)

Then why are you adding 2 again ? If to show constant time then 
T(n-1) + T(n-3)+1 would be correct ?

Correct me if wrong !

0
gokhu for any value grater than equal to 1 . minimum 2 function calls i.e. get (n-1);  and get (n-3);

take n= 1 then get(0) and get(-2) .isnt?
0

@Anirudh  SIR It is being represented in Recurrence Relation . Then Why 2 getting added ? That part not clear

+3
take n = 2 then aplly given program and then do with reccurence given with same value of n then you will get.
+15

Reason for '2 ' in Recurrence Relation in marked as 1 and 2.

g( n-1) 

g(n-3)

These two calls are present in every sussessive function calls .  Hence 2

0
Thx :)
+1
T(1)= T(0)+T(-2)

ISNT IT EQUAL TO 3 CALLS??
0
@sushmita : Nope it constitutes two calls only because invoking call does not count

for example : Fib(2) will call fib(1) and fib(0) not fib(2) .

PS : fib is an example of standard Fibonacci sequence recursive procedure.
+3
invoking call also accounts in total no of calls. Thats why answer is 24+1 that is 25.
0
I think that 1 is main call "get(6)" it will also invoke get function at very initial stage.And thats why invoking get(0) is counted as 0 not 1?
0
What will printf return? Is it this:

123141251236
0
how g(5) are making 16 invocations?

g(5)=g(4)[calls=10] +g(2)[calls=4]

If g(5) is called from main it will be main[1] + 10 + 4 =15 right?
0
WHAT DOES CALL FROM MAIN() MEANS?
0

@ @Arjun sir

T(n) = T(n-1) + T(n-3) + 1         , n >0

T(n) = 1                                     ,n <=0

is this equation is also right ??

0

@jatin khachane 1 For any positive value.... there are two direct invocations. So it should be +2.

0
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

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

Answer: B. 25

by Active (1.6k points)
0
Can u plzzz explain..plzz...!!
0 votes
by (407 points)
0
can u explain what they hav done ?? i am nt getting it ..
–1 vote

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

by Junior (563 points)
0
Yes.   Tree will be also better
0
+1 or +2 ??
0
What do you mean by +1+2?
0

 T(n) = T(n-1) + T(n-3) +1 or  T(n) = T(n-1) + T(n-3) +2 ??? Still its wrong as its not  T(n) = 1 ....

+1

Please note question is asking about invokaton so we have to calculate every time a function is called .. hope this picture clears it 

0

Refer to https://gateoverflow.in/507/gate1991_01-x . same type of question.

+1
When g(1) is called,I guess there is no need to call g(0) and g(-2) because when n ==1, the function gets returned so there won't be any further calls to it from that point. Correct me if I'm wrong.
+2
function gets returned when n<1 not when n<=1.
0

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

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,491 answers
195,438 comments
100,672 users