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

Let's analyze both functions carefully.

Function foo

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

The key point is post-decrement:

foo(val--)

passes the current value of val to the recursive call, and only then decrements val.

Suppose we call:

foo(3)

Inside the loop:

foo(val--)

becomes

foo(3)

and only after the call returns would val become 2.

But the call is foo(3) again, which immediately calls foo(3) again, and so on.

Thus the recursion never progresses toward a base case.

Result: infinite recursion → stack overflow → abnormal termination.

---

Function bar

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

For bar(3):

while(val > 0)

and notice that val is never modified inside the loop.

The recursive call:

bar(val - 1)

eventually reaches:

bar(0)

which returns normally.

However, after that return, we are still inside:

while(val > 0)

with val == 1 (or 2, or 3 depending on the level), and val never changes.

Therefore the loop runs forever.

Result: infinite loop.

---

Conclusion

• foo(3) → abnormal termination (infinite recursion / stack overflow)
• bar(3) → infinite loop

Answer: C. Abnormal termination and infinite loop respectively.

---

 

Taking  val=1 ;  makes this loop work infinite,  basically bar(0) will  be called again and again , we are not calling bar(1) multiple times,  it is while loop which is calling bar(0) again and again.

while(1> 0) { //val=1

        x= x + bar(val-1);

    }

---

$$\text{bar(3)}$$

 

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

 Your answer 1 is inaccurate, what do you mean by the function not running infinitely because the val is decremented when you said this?

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

here the val is surely not decremented in no iteration that is the whole point we are not able to exit properly, but it does not run into infinite loop because it keeps calling the function foo(val) with the same value every time, meaning for each call we are adding an activation record to the recursion stack, and when you cross the limit you get memory exceeded, 

 

This does not happen in the second case "bar", you have taken good example but failed to explain more, when you do bar(3), it goes like this
 

bar(3) -> bar(2) -> bar(1) -> bar(0) -> returns to bar-1 -> bar(0) -> returns to bar-1 -> bar(0) -> ......

here you can see once bar(0) is called it return to bar(1) meaning the activation record is removed, and again when it comes to bar(1), bar(0) is called, a new activation record is created, thus the activation record for bar(0) is continuously added and removed, if the function can successfully reach bar(1) without StackOverflow it should not have any problem accommodating 1 more activation record and thus memory leak never happens and the function flows infinitely, 

Hope this helped

---

Best explanation brother!

---

If in place of option C can we give both are infinite loops ??

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

---

Explanation is perfect but all other answers lack one thing, Bar function, how infinite loop?

Let me answer: bar(3) -> bar(2) -> bar(1) -> bar(0),

here bar(0) will return 0 to bar(1),

so in bar(1) next step will be x = 0 + 0{return by bar(0)} ;

then curly bracket will be executed. after this,

while loop will be checked whether condition is true or not.

 as val =1 in bar(1), so again it will execute x = x + bar(val -1 ) which is bar(0) and hence loop will be there infinite times.

here 4thstack depth will be filled with bar(0) and then again popped then again filled with bar(0)......., stack depth is not increasing (not stack overflow) but looping around hence infinite loop

Thank you

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

Answer 5

May Be It Works :

Answer 6

In bar function,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(while 0>0) is 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 bar 1 which is while(1>0)...

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

Also,In foo function,val-- means post decrement operator.so val is decremented only in the next statement.so foo(val--) means foo3 calls foo3..foo3 calls foo3..foo3 calls foo3 repeatedly causing abnormal termination of the program.

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

Comments

U say bar 0 means condition false which condition is false in your achknoledgement ......

---

It's the while condition. while(0>0) here.