GATE CS 2018 Q.55 (CS Q.45): Functions, Recursion, Scope and Storage Classes

Consider the following program written in pseudo-code. Assume that x and y are integers.

Count(x,y) { 
    if (y != 1){   
        if (x != 1) { 
            print("*"); 
            Count(x/2, y); 
        } 
        else { 
            y = y-1; 
            Count(1024, y); 
       } 
   } 
}

The number of times that the print statement is executed by the call Count(1024,1024) is _____.

Your answer

Official answer and solution

Official answer: 10230
From: Official GATE 2018 answer key

Solution

Analyze loop iterations and recursive invocations to count print executions.

Trace the recursive execution of Count(x, y) when invoked with Count(1024, 1024):

While $y \neq 1$ , for a fixed $y$ , x starts at 1024.
In each step where $x \neq 1$ , it executes print("*") and recurses with Count(x/2, y).
The values of $x$ for which $x \neq 1$ are: $1024, 512, 256, 128, 64, 32, 16, 8, 4, 2$ (exactly 10 values). Each prints one *.
When $x = 1$ , the else branch executes: $y$ is decremented by 1 ( $y = y - 1$ ), and it calls Count(1024, y).

This cycle repeats for every value of $y$ from 1024 down to 2:

y = 1024, 1023, \dots, 2

The number of such values of $y$ is $1024 - 2 + 1 = 1023$ .

When $y = 1$ , the outer condition if (y != 1) is false, and the function terminates without printing.

Total print executions:

\text{Total} = 1023 \times 10 = 10230

Final answer

10230

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: 55 of 65, printed as CS Q.45
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