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

The Gateway to Computer Science Excellence

+40 votes

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

- $15$
- $25$
- $35$
- $45$

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

+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

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

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

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?

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

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

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.

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

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?

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

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

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

0

+1

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,491 answers

195,438 comments

100,672 users