Manas Chaturvedi - 1 year ago 80
Python Question

# Finding if a number is a power of 2 using recursion

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?

``````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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download