The GATE Grind

GATE 2017 CS – Question 46

Programming and Data Structures · Recursion · 2 marks · Multiple choice

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:

  1. Return of 6 and 6 respectively.
  2. Infinite loop and abnormal termination respectively.
  3. Abnormal termination and infinite loop respectively.
  4. Both terminating abnormally.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Abnormal termination and infinite loop respectively.

Explanation

In `foo`, the call `foo(val--)` passes the current value of `val` before decrementing it, so the recursive call has the same argument and recurses forever, which ends in a stack overflow (abnormal termination). In `bar`, the recursion `bar(val - 1)` reaches 0 and returns, but the `while` loop in each call never changes `val`, so the loop never ends. That is an infinite loop.