IAE Academy

GATE 2020 CS Q.46: solution and answer

GATE 2020 · CSQ.46 · 2 marks · NAT

Consider the following C functions.

int fun1(int n) {
  static int i = 0;
  if (n > 0) {
    ++i;
    fun1(n-1);
  }
  return(i);
}
int fun2(int n) {
  static int i = 0;
  if (n > 0) {
    i = i + fun1(n);
    fun2(n-1);
  }
  return(i);
}

The return value of fun2(5) is ______.

See the question in the paper
GATE 2020 CS question 46Tap to open full size

Answer and solution

ANSWER

The return value of fun2(5) is 55.

Official answer: 55Source: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Note fun1's static variable (call it j) and fun2's static variable (call it i) are each shared across ALL calls to that respective function — they are initialized once, not per call.

  2. fun1(n) with n>0 increments j once then calls fun1(n-1); the base case (n=0) just returns j. So a call fun1(n) increments j exactly n times before returning it (in decreasing order n, n-1, ..., 1).

  3. Trace fun1's static j (starts at 0) across the successive top-level calls made by fun2: fun1(5) increments j by 5 → j=5, returns 5. fun1(4) then increments j by 4 more → j=9, returns 9. fun1(3) adds 3 more → j=12, returns 12. fun1(2) adds 2 more → j=14, returns 14. fun1(1) adds 1 more → j=15, returns 15.

  4. Trace fun2's static i (starts at 0): fun2(5): i = 0 + fun1(5) = 0+5 = 5, then calls fun2(4).

  5. fun2(4): i = 5 + fun1(4) = 5+9 = 14, then calls fun2(3).

  6. fun2(3): i = 14 + fun1(3) = 14+12 = 26, then calls fun2(2).

  7. fun2(2): i = 26 + fun1(2) = 26+14 = 40, then calls fun2(1).

  8. fun2(1): i = 40 + fun1(1) = 40+15 = 55, then calls fun2(0), whose base case (n=0) just returns i = 55 unchanged.

  9. Because every level's return(i) executes only after its recursive call has already returned, and nothing after the recursive call modifies i, every level of fun2 — including the outermost fun2(5) — returns the same final shared value, 55.

KEY IDEA

Each function has its OWN static variable, shared across every recursive call to that function (not per-call). fun1's static i accumulates once per call to fun1, so fun1(n) returns the running total after n more increments. fun2's static i accumulates fun1(k)'s return value at each level and is returned unchanged by every subsequent (deeper) fun2 call, since nothing decrements it afterward.

WATCH OUT FOR

Treating fun1's static i as reset to 0 on every fresh call from fun2 (as if it were an ordinary local variable), which makes each fun1(k) call return only k instead of the running cumulative total — this undercounts every term after the first and gives an answer far smaller than 55.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 9 Recursion questions, with notes

More Recursion questions