技术咨询：递归函数int f(int n)的返回值含义及规律求解

Hey there! Let's break down this function line by line to uncover what it's actually calculating. First, let's restate the function clearly:

int f(int n){ 
    if(n == 0) return 0; 
    else return n % 2 + f(n / 2); 
}

Let's unpack the logic step by step: #

• The base case is straightforward: when n is 0, return 0.
• For any non-zero n, we do two key things:
  1. n % 2 gives us the least significant (rightmost) bit of n's binary representation. This will be 1 if n is odd, 0 if even.
  2. f(n / 2) is the recursive call: integer division by 2 shifts n's binary representation one bit to the right (dropping that least significant bit we just checked).

Each recursive call essentially adds up each bit of n's binary form, one by one, starting from the rightmost bit.

Let's test with examples to confirm: #

• If n = 5 (binary 101):
  f(5) = 5%2 + f(2) = 1 + (2%2 + f(1)) = 1 + 0 + (1%2 + f(0)) = 1+0+1+0 = 2 → which is exactly the number of 1s in 101.
• If n = 7 (binary 111):
  f(7) = 1 + f(3) = 1 + 1 + f(1) = 1+1+1+0 = 3 → matches the three 1s in its binary form.
• If n = 8 (binary 1000):
  f(8) = 0 + f(4) = 0 + 0 + f(2) = 0+0+0+f(1) = 0+0+0+1+0 =1 → correct, only one 1 here.

In short: #

This function returns the count of 1 bits in the binary representation of n—also known as the Hamming weight of the integer n.

内容的提问来源于stack exchange，提问作者Jonathan