Finding if a number is a power of 2 using recursion

Question

I'm trying to find whether a number is a power of 2 using recursion. However, I couldn't seem to figure out the correct solution. Here's what I've tried so far:

def is_power(n):
    n = n/2
    if n == 2:
        return True
    elif n > 2:
        is_power(n)
    else:
        return False


if is_power(32):
    print 'yes'
else:
    print 'no'

Since '32' is a power of 2, I expected my code to return 'yes' as the output. However, the code outputs 'no' instead. What seems to be wrong with my code?

Answer 1

elif n > 2:
    is_power(n)

is missing the return:

def is_power(n):
    n = n/2
    if n == 2:
        return True
    elif n > 2:
        return is_power(n)
    else:
        return False

thus, the "first" level of is_power returns nothing (or None, depending on how you check), which leads to output of no.

@kaveman correctly pointed out is_power(2) yields the wrong result. You can fix that by halving 2 in the elif clause:

def is_power(n):
    if not n == int(n):
        return False
    n = int(n)
    if n == 1:
        return True
    elif n > 2:
        return is_power(n/2.0)
    else:
        return False

EDIT: @will pointed out that I was mixing up python2 with python3 division. Using /2.0 fixes that. Also, in comments to the question he pointed out that 1 is a power of 2. Checking against ==1 instead of ==2 fixes that issue. Also, I added an int cast, which is not necessary for the power of 2 check (since well, IEEE754 floats are base 2 after all, so powers of 2 are exactly representable), but for non-2 bases, this will make the code portable.