Manas Chaturvedi - 1 year ago 66

Python 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 Source

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