The GATE Grind

GATE 2017 CS (CS1) – Question 45

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

Consider the following two functions.

void fun1(int n) {
    if(n == 0) return;
    printf("%d", n);
    fun2(n - 2);
    printf("%d", n);
}

void fun2(int n) {
    if(n == 0) return;
    printf("%d", n);
    fun1(++n);
    printf("%d", n);
}

The output printed when `fun1(5)` is called is

  1. 53423122233445
  2. 53423120112233
  3. 53423122132435
  4. 53423120213243

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 53423122233445

Explanation

Trace the mutual recursion. Note that `fun2` increments `n` (`++n`) before passing it to `fun1`, and the later print in `fun2` uses the incremented value.

Calls going down:
1. `fun1(5)` prints **5**, calls `fun2(3)`.
2. `fun2(3)` prints **3**, calls `fun1(4)` (n becomes 4).
3. `fun1(4)` prints **4**, calls `fun2(2)`.
4. `fun2(2)` prints **2**, calls `fun1(3)` (n becomes 3).
5. `fun1(3)` prints **3**, calls `fun2(1)`.
6. `fun2(1)` prints **1**, calls `fun1(2)` (n becomes 2).
7. `fun1(2)` prints **2**, calls `fun2(0)` which returns immediately.

Returning back up:
- `fun1(2)` prints **2**
- `fun2(1)` prints its `n=2`: **2**
- `fun1(3)` prints **3**
- `fun2(2)` prints its `n=3`: **3**
- `fun1(4)` prints **4**
- `fun2(3)` prints its `n=4`: **4**
- `fun1(5)` prints **5**

Output: `5 3 4 2 3 1 2` then `2 2 3 3 4 4 5` $=$ **53423122233445** (option A).

More Recursion questions

All Recursion questions →