Give a recursive definition of the function ones(s) which counts the number of ones in a bit string s.

Answer 1

Is it a pseudocode or algorithm that you are looking for?

Counting the number of ones in a string of size n is of order O(n), whether by a recursive function or by marching, since every bit has to be examined.