Consider the following recursive C function that takes two arguments. unsigned…
2011
Consider the following recursive C function that takes two arguments.
unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; }
What is the return value of the function foo when it is called as foo(513, 2)?
- A.
9
- B.
8
- C.
5
- D.
2
Attempted by 346 students.
Show answer & explanation
Correct answer: D
Key idea: for r = 2, the function returns the sum of n%2 at each step while repeatedly doing n = n/2. That sum equals the number of 1 bits in n's binary representation.
Compute successive remainders for n = 513:
513 % 2 = 1 → n becomes 256
256 % 2 = 0 → 128 % 2 = 0 → 64 % 2 = 0 → 32 % 2 = 0 → 16 % 2 = 0 → 8 % 2 = 0 → 4 % 2 = 0 → 2 % 2 = 0
1 % 2 = 1 → then n becomes 0 and recursion stops
Add the remainders: 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 2.
Conclusion: foo(513, 2) returns 2.
A video solution is available for this question — log in and enroll to watch it.