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 _____.
ANSWER
The print statement runs 10230 times.
Official answer: 10230Source: Official answer key, GATE 2018 CS (IIT Guwahati)
While y ≠ 1 and x ≠ 1, each call prints one * and calls Count(x/2, y). Starting from x = 1024 = 2¹⁰, x takes the values 1024, 512, …, 2 before it reaches 1, so one round prints 10 stars.
When x reaches 1, the else branch runs: y decreases by 1 and the next call restarts x at 1024.
The rounds run for y = 1024, 1023, …, 2, which is 1023 rounds. When y becomes 1 the outer test y != 1 fails and the recursion stops without printing.
Total prints = 1023 × 10 = 10230.
KEY IDEA
Count the prints in one round of halving and multiply by the number of rounds: every value of y from 1024 down to 2 runs one full halving of x from 1024 to 1, and y = 1 ends the recursion.
WATCH OUT FOR
Counting 1024 rounds instead of 1023 (the call with y = 1 prints nothing), or 11 prints per round instead of 10 (there is no print once x = 1). Either slip gives 10240 or 11253 instead of 10230.
From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 9 Recursion questions, with notes
