Question

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

Accepted Answer

The correct answer is 10230. For each fixed value of y (as long as y≠1), x halves from 1024 down to 1, printing once per halving — that's 10 prints per 'cycle' (1024→512→...→1, ten halvings). After x reaches 1, y decrements by 1 and x resets to 1024, starting a new cycle. This repeats for y = 1024, 1023, ..., 2 (1023 values of y, since y=1 stops the recursion with the outer if failing) — each contributing 10 prints. Total = 1023 × 10 = 10230.

Explanation