Writing a recursive function that sums up the number of values, with odd binary number of 1s, in pseudocode

Question

I have a homework question that states:

Write a recursive function sum_odd(n), using the pseudocode principles covered in the lecture, to sum up the numbers i between 1 and n where the binary representation of i contains an odd number of 1s, e.g., 14 is represented as 0b1110 which contains an odd number of 1s. You can assume that you have access to a function binary_ones(d), which returns the number of ones in the binary representation of d. You should not write out this function, but can call it in your pseudocode. You may also assume that n will be greater than 0 – error checking is not needed.

So far, I have come up with this:

function sum_odd(n):
    read n 
    sum = 0 
    if n is less than or equals to 0 then
         return sum
    else if binary_ones(n) % 2 equals 1 then
         return sum = sum + sum_odd(n-1)
    else
         return sum_odd(n-1)
    end if 

What I am concerned with is the sum = sum + sum_odd(n-1) part. I don't think it will add the first value that is entered which is making me doubt if I even did it right.

Could use some help.

Answer 1

I don't have enough reputation to comment yet, so I will post this as an answer.

So here is what I think are some flaws in your pseudo-code-

1. You don't need to read n, it is passed as an argument, so read n should be be done by the main function which calls sum_odd(n).
2. Your concern is right, it shouldn't be return sum = sum + sum_odd(n-1) it should be return n + sum_odd(n-1). You didn't do the sum up the numbers part, you didn't add the number which satisfied the condition.
3. You don't need sum = 0 variable, you could just return 0 for n <= 0 condition.