What does this recursive function return?
FUNCTION Mystery(N : INTEGER) RETURNS INTEGER
IF N = 0 THEN
RETURN 0
ELSE
RETURN (N MOD 2) + Mystery(N DIV 2)
ENDIF
ENDFUNCTION
What value is returned by Mystery(13)?
A 3
B 6
C 13
D 1101
[1]
- 1
Trace the calls. Mystery(13) = 1 + Mystery(6); Mystery(6) = 0 + Mystery(3); Mystery(3) = 1 + Mystery(1); Mystery(1) = 1 + Mystery(0); Mystery(0) = 0.
- 2
Unwind. 0 + 1 + 1 + 0 + 1 = 3. Answer A (1).
The function adds up the remainders when dividing by 2, which are the binary digits of N (13 = 1101), so it counts the 1 bits.
Answer
A
Examiner tip
Examiner tip: write each call on its own line with the value it is waiting to add, then add up from the base case. That is the unwinding the syllabus refers to.
Common mistake: choosing D. The function adds the remainders; it does not join them into a binary number.