GATE CS 2018 Q.31 (CS Q.21): Functions, Recursion, Scope and Storage Classes

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

Your answer

Official answer and solution

Official answer: 4
From: Official GATE 2018 answer key

Solution

Trace the recursive calls to count how many times the function is invoked.

The function calc(a, b) increments the global variable counter upon entry, checks if $b == 3$ , and if not, recursively calls calc(a, b/3).

Trace the recursive invocations starting from calc(4, 81):

calc(4, 81): counter becomes 1. Since $81 \neq 3$ , calls calc(4, 27).
calc(4, 27): counter becomes 2. Since $27 \neq 3$ , calls calc(4, 9).
calc(4, 9): counter becomes 3. Since $9 \neq 3$ , calls calc(4, 3).
calc(4, 3): counter becomes 4. Since $3 == 3$ , base case is reached and returns $4^3 = 64$ without further recursion.

The total number of invocations is 4, so counter equals 4.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 31 of 65, printed as CS Q.21
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source