Python递归代码求是否是二的幂

好的,我很乐意为您解释如何使用Python递归代码来判断一个数是否是2的幂。以下是一个实现这个功能的Python函数:

def is_power_of_two(n):
    # 基本情况: 0不是2的幂,1是2的幂
    if n == 0:
        return False
    if n == 1:
        return True
    
    # 如果n是偶数,继续递归
    if n % 2 == 0:
        return is_power_of_two(n / 2)
    else:
        # 如果n是奇数,且不等于1,则不是2的幂
        return False

# 测试函数
print(is_power_of_two(16))  # True
print(is_power_of_two(18))  # False
print(is_power_of_two(1))   # True
print(is_power_of_two(0))   # False

这个递归函数的工作原理如下:

1. 首先,我们处理两个基本情况:0不是2的幂,1是2的幂。

2. 然后,我们检查n是否是偶数。如果是,我们将n除以2,并递归调用函数。

3. 如果n是奇数,我们检查它是否等于1。如果等于1,说明之前的递归调用已经将n除到1,这是一个2的幂。如果不等于1,说明n不是2的幂。

4. 函数会一直递归调用自己,直到n被除到1(如果是2的幂)或遇到奇数(不是2的幂)。

这个方法的时间复杂度是O(log n),因为我们每次都将n除以2。