Programming Basics (Pseudocode Tracing)
÷ is division; when the result is assigned to an integer variable (including a function argument), the fractional part is discarded. When the following function pow is called as pow(2, 10), how many times is pow called, including the first call?
○integer: pow(integer: x, integer: n)
if (n = 0)
return 1
endif
integer: h ← pow(x, n ÷ 2)
if (n mod 2 = 0)
return h × h
endif
return h × h × x- A5
- B10
- C11
Show answer and explanation
Answer: A. 5
pow(x, n) computes x to the power n by squaring the result of pow(x, n ÷ 2) with n halved (multiplying by x once more when n is odd). n changes to 10, 5, 2, 1 and 0, and the recursion stops at n = 0, so pow is called 5 times. The return value is 2¹⁰ = 1024. Decreasing n by 1 at a time, as in x × pow(x, n − 1), would make 11 calls, from n = 10 down to 0. Halving n makes the number of calls grow roughly in proportion to log₂ n.
- A. Correct. n = 10, 5, 2, 1, 0: five calls.
- B. This is the exponent n = 10. n is halved, not decreased by 1.
- C. This is the number of calls when n decreases by 1 each time (x × pow(x, n − 1)).
Continue: 9 more Programming Basics (Pseudocode Tracing) questions