Consider the following recursive C function that takes two arguments unsigned…

2020

Consider the following recursive C function that takes two arguments 

unsigned int rer (unsigned int n, unsigned int r) {
  if (n > 0) return (n% r + rer(n/r, r));
  else return 0;
 }

What is the return value of the function rer when it is called as rer (513, 2) ?

  1. A.

    9

  2. B.

    8

  3. C.

    5

  4. D.

    2

Attempted by 294 students.

Show answer & explanation

Correct answer: D

Step-by-Step Trace of rer(513, 2)

What does this function do?
It converts number n to base r and returns sum of digits in that base!

c

return (n % r + rer(n/r, r));
// n%r = last digit in base r
// rer(n/r, r) = sum of remaining digits

Recursive Trace:

Call

n

r

n%r

n/r

Returns

rer(513, 2)

513

2

1

256

1 + rer(256,2)

rer(256, 2)

256

2

0

128

0 + rer(128,2)

rer(128, 2)

128

2

0

64

0 + rer(64,2)

rer(64, 2)

64

2

0

32

0 + rer(32,2)

rer(32, 2)

32

2

0

16

0 + rer(16,2)

rer(16, 2)

16

2

0

8

0 + rer(8,2)

rer(8, 2)

8

2

0

4

0 + rer(4,2)

rer(4, 2)

4

2

0

2

0 + rer(2,2)

rer(2, 2)

2

2

0

1

0 + rer(1,2)

rer(1, 2)

1

2

1

0

1 + rer(0,2)

rer(0, 2)

0

2

—

—

0 (base case)

Adding Up:

= 1+0+0+0+0+0+0+0+0+1+0
= 2

Verification — 513 in Binary:

513 = 512 + 1
    = 2⁹  + 2⁰
    = 1000000001 (in binary)

Binary digits: 1,0,0,0,0,0,0,0,0,1

Sum of binary digits = 1 + 1 = 2

Final Answer: rer(513, 2) = 2

Shortcut: This function always returns the count of 1s in the binary representation of n (when r=2), also known as the Hamming Weight or Population Count!

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Isro