Write a recursive method that returns the number of 1s in the binary representation of N

Uppgift:

Write a recursive method that returns the number of 1s in the binary

representation of N. Use the fact that this number equals the number

of 1s in the representation of N/ 2, plus 1, if N is odd.

 

Uppgiften är från boken 'Data Structures and Problem Solving Using Java'.

Nu var jag så busig och kollade facit till uppgiften och försöker nu att begripa stegen i i varje rekursionsanrop som slutligen leder till basfallet. Nedan har jag klistrat in lösningen enligt facit följt av min tolkning av vad som händer i varje steg. Om jag fått något om bakfoten så vore jag enormt tacksam för respons

Facit:

//The method below assumes that N is positive.

public static int numOnes( long n )

{

     if( n <= 1 )

          return n;

     else

          return numOnes( n / 2 ) + n % 2;

}

Min tolkning:

Jag testar N = 11 (som är 1011 i binärform -> tre stycken 1:or):

Steg 1: numOnes(11) → return numOnes(11/2) + 11%2 → return numOnes(5) + 1
Steg 2: numOnes(5) → return numOnes(5/2) + 5%2 → return numOnes(2) + 1
Steg 3: numOnes(2) → return numOnes(2/2) + 2%2 → return numOnes(1) + 1
Steg 4: numOnes(1) → {“hoppar in” i basfallet ty N = 1 <= 1} → return N → return 1 = numOnes(1) 
Steg 3: numOnes(1) + 1 = 1+1 = 2 = numOnes(2) ->
Steg 2: numOnes(2) + 1 = 2+1 = 3 = numOnes(5) ->
Steg 1: numOnes(5) + 1 = 3 + 1 = 4

Mitt resultat blir 4, men med N=11 så bör väl resultatet bli 3?