IAE Academy

GATE 2018 CS Q.21: solution and answer

GATE 2018 · CSQ.21 · 1 mark · NAT

Consider the following C program:

#include <stdio.h>

int counter = 0;

int calc (int a, int b) {
    int c;

    counter++;
    if (b==3) return (a*a*a);
    else {
        c = calc(a, b/3);
        return (c*c*c);
    }
}

int main (){
    calc(4, 81);
    printf ("%d", counter);
}

The output of this program is _____.

See the question in the paper
GATE 2018 CS question 21Tap to open full size

Answer and solution

ANSWER

The output of the program, and the value printed for counter, is .

Official answer: 4Source: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. counter is a global variable, initialized to 0. It is incremented by exactly one at the very start of every call to calc, before any recursion or return happens, and it is never touched anywhere else in the program.

  2. main calls calc(4, 81) once, then prints counter (the returned value of calc is never used or printed — the c*c*c computations affect only the function's return value, not counter).

  3. Trace the calls by the value of b, using integer division b/3: calc(4,81): b=81≠3 → counter becomes 1 → calls calc(4, 81/3) = calc(4,27).

  4. calc(4,27): b=27≠3 → counter becomes 2 → calls calc(4, 27/3) = calc(4,9).

  5. calc(4,9): b=9≠3 → counter becomes 3 → calls calc(4, 9/3) = calc(4,3).

  6. calc(4,3): b==3 → counter becomes 4 → returns a*a*a = 64 directly, with no further recursive call (base case reached).

  7. The recursion now unwinds: calc(4,9) receives c=64 and returns 64*64*64; calc(4,27) receives that value and returns its cube; calc(4,81) does the same. None of these unwinding steps call calc again, so counter is not incremented any further.

  8. Exactly 4 calls to calc occurred in total (b = 81, 27, 9, 3), so counter ends at 4, and printf("%d", counter) prints 4.

KEY IDEA

A global variable incremented once per function call counts the number of times that function executes; here calc recurses on b/3 until b==3, so the count equals the number of times 81 can be divided by 3 to reach 3, i.e. , giving 4 calls.

WATCH OUT FOR

Confusing the returned value of calc (a large cubed-and-recubed number, 64 cubed three times over) with what is actually printed; the program never prints the return value of calc, only the unrelated call-count counter, so trying to compute (((64)^3)^3)^3 is wasted effort and not the answer being asked for.

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

More Recursion questions