GATE 2018 CS – Question 55

Programming and Data Structures · Recursion · 2 marks · Numerical answer

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 10230

Explanation

For a fixed $y$, $x$ goes $1024\to512\to\dots\to1$, printing 10 times before $x=1$ triggers `y=y-1` and a reset to 1024. This happens for $y=1024,1023,\dots,2$, which is 1023 values of $y$, so $10\times1023=10230$ prints.