GATE CSE 2017 Set 1 | Question: 36

Question

Consider the C functions foo and bar given below:

int foo(int val) {
    int x=0;
    while(val > 0) {
        x = x + foo(val--);
    }
    return val;
}

int bar(int val) {
    int x = 0;
    while(val > 0) {
        x= x + bar(val-1);
    }
    return val;
}

Invocations of $foo(3)$ and $bar(3)$ will result in:

• A. Return of $6$ and $6$ respectively.
• B. Infinite loop and abnormal termination respectively.
• C. Abnormal termination and infinite loop respectively.
• D. Both terminating abnormally.

Comments

Val value in bar function is always 3

Am I right!

---

Question:- Why there is abnormal termination in bar()

It will also fill stack by calling bar(1) multiple times????

---

Usefull comment

bar 3 calls bar 2..bar 2 calls bar 1..bar 1 calls bar 0...now comes the concept..

return 0 transfers the control to while(1>0) condition and we know that this condition in while loop means while loop will execute infinitely..

Please go through the previous question(GATE2017-1-35 )for clarity about the return statement...

Answer 1

Answer should be C.

Consider $foo$ 

Initially $val=3$ 

$foo(val--)$

is equivalent to

1. $foo(val)$
2. $val=val-1$

So,

1. $foo(3)$
2. $val=2$

$foo(3)$ calls $foo(3)$ which in turn calls $foo(3)$ this goes on 

So, here we can see that $foo(3)$ is called infinite number of times which causes memory overflow and abrupt termination

and one more thing to observe is infinite loop is not there since the val is decremented in the first iteration. 

Consider bar.

Here, we can see the val is not decrementing in the loop

So,

1. $bar(3)$ will call $bar(2)$
2. $bar(2)$ will call $bar(1)$
3. $bar(1)$ will call $bar(0)\qquad \to$ Here, $bar(0)$ $return\;0$ 
4. $bar(1)$ will call $bar(0)$
5. $bar(1)$ will call $bar(0)$

This will go on so here there is a problem of infinite loop but not abrupt termination since it does not cause memory overflow.

Comments

I am not able to understand the bar part could you please elaborate the statement that bar(1) will not return ?

---

Check the while loop ... is there any statement which is reducing the value of val ?? No right ... So infinite loop ...

---

Both initially goes to infinite loop, but the first one terminates abruptly but second run still infinite. Why? it is not clear.

#include <stdio.h>

int main(void) {
    // your code goes here
    printf("%d",foo(3));
    return 0;
}

int foo(int val) {
    int x=0;
    printf("Hello");  /// Here everything looks clearly
    while(val > 0) {
        x = x + foo(val-1);
    }
    return val;
}
Why this happen, plz explain someone.

---

I am not able to understand the bar function? Anyone help with this?

---

val-1 decreases val by 1..so bar 3 calls bar 2..bar 2 calls bar 1..bar 1 calls bar 0..bar 0 means condition false therefore return 0..

Now, return 0 ..return statement definition is it should terminate the current function bar 0 and transfer the control to the calling function while(1>0)...

while(1>0) means infinite loop...so ans is C

---

Yeah..Got it!!

Thank you so much

---

why bar1 will call bar0 multiples times?

in the first time only it will get back value as 0 (x=x+bar(0)=x+0=0+0=0)  from bar0.

Why is this not propagated to bar2,bar3 ???

Please explain ......

---

Yeah you are right,now calculated value is assigned to x,after which the loop continues,i.e.,

Int bar(int val){

While(val>0)

{

x=x+bar(val-1);

/*after x=0+0; the loop is checked again,as value of val is 1 in this activation record(current function),while condition becomes true again ((val)1>0).it enters the loop again bar(val(1)-1) is called i.e., bar(0) which in turn returns 0,again x=0+0; again checks the loop,again calls ....*/

}

return val;/*this line gets executed only when the while loop becomes false.*/

}

Note: you have to re-trace to clearly understand,that return 0 happens  only when while loop becomes false,in our case only when bar(0) is called while loop becomes false.

---

by the use of stack ,,,,we can clearly, understand this problem

---

I couldn't understand first because my sub-conscious mind treated while loop as if condition, this is kind of semi-googly question.😁

---

It meas var-- and var-1 are not same?

---

@arpit_18 yess , in var- – , var has post decrement but in  var-1  we use the the decremented value  of var but we doesnot decrement the value of var.

hope you got it :)

---

@sristicse Got it, Thanks :)

---

Why bar(0) is called multiple times?

When bar(1) is called then, val=1, x=0 and while(1>0) condition true.   x=x+bar(1-1) => x=x+bar(0)

Now since it is executing while loop it cannot leave the loop until the condition become false. So, again while (1>0) then bar(0) again called and this repeats. when bar(0) is executing then val=0 and it is returning 0. Activation record of bar(0) is out from the stack and we are left with bar(1) whose val=1 (reason).

We can do minor improvements to fix this code :

---

ASNR1010

got it!👍

---

One common doubt is “in both cases infinite times functions are invoked” then why ans is not “infinite loop in both cases”
The reason is:
For function foo()

foo(3)  gets invoked infinite times. So the stack is getting filled.
So memory overflow will occur, resulting in abnormal termination for foo() .

Now for Bar()

Bar(3) invokes Bar(2) which then invokes Bar(1)
 Bar(1) invokes Bar(0).
Then Bar(0) is executed and the control returns back to Bar(1).
Again Bar(0) called , it gets executed and this cycle continues.
So you can see almost 4 function calls remain in stack .
So no chance of memory overflow. But there is an infinite loop of function call and execution.
So it is an infinite loop for the bar().
U can refer to the following pic for better clarity of execution of bar().
Pic credits: @[+Jiren+] (https://gateoverflow.in/user/%5B+Jiren+%5D)

 

---

in such a type of recursion:

• when do we say it goes to an infinite loop?
• when do we say it gives memory overflow/abnormal termination?

---

very nice explanation

---

when the stack is going to full means repeatedly function is calling and stack memory is overloaded at a certain time then it will be terminated by the compiler 

when the process inside  while loop being executed multiple times and hoing to infinity then its called infinite loop.

Answer 2

ans C.

Comments

Why have you crossed return 0;

---

Please  someone explain could not get the bar  part

---

nice 2018 ,,,,m also approach same

Answer 3

int foo(int val) {
    int x=0;
    while(val > 0) {
        x = x + foo(val--); 
        
/* Post decrement operator
That means foo() will be recursively called with the same value,
and after that val would be decremented.
That recursively called function will do the same in itself.
Hence, we got an infinite sequence of foo(3) --> foo(3) --> foo(3) so on.
At some point, the stack would overflow, hence abnormal termination.*/

    }
    return val;
}

---

---

int bar(int val) {
    int x = 0;
    while(val > 0) {
        x= x + bar(val-1);
        
/* bar(3) --> bar(2) --> bar(1) --> bar(0)
bar(0) would return. Back to bar(1) Val is still 1, so call bar(0)
bar(0) would return again.
Hence we got an infinite sequence of bar(1) --> bar(0) --> return to bar(1)
--> call bar(0) --> return to bar(1) --> call bar(0); so on.
Hence, ininite loop.*/

    }
    return val;
}

---

 

Option C

PS: Why not infinite loop in foo() ?
Because we're not technically looping around. Each foo(3) calls a new foo(3). If you make a control flow diagram, the arrow would never go backwards.

For bar() the same bar(1) keeps calling bar (0) over and over.

Comments

Thanks a ton for this explanation. Finally i got it. I also find all your answers very helpful.

Thanks.

---

Thanks a ton, brother. Means a lot ^_^

---

Where does the difference come when the statement x=x+bar(val-1) is replaced by x=x+bar(--val);

---

@ zoboknows Very correct!

Answer 4

Ans is C.
Foo(3) will give runtime error on any compiler i.e stack overflow hence abnormal termination. (You know about Post decrement)
bar(3) will not stop at all, some compilers will terminate it forcefully. Infinite Loop. 

Comments

can someone explain what actual problem is with bar?

---

awesome question...

---

bar 3 calls bar 2..bar 2 calls bar 1..bar 1 calls bar 0...now comes the concept..

return 0 transfers the control to while(1>0) condition and we know that this condition in while loop means while loop will execute infinitely..

Please go through the previous question(GATE2017-1-35 )for clarity about the return statement..