如何用递归实现不使用math库与%运算符判断一个数是否为另一个数的幂

前置约定 #

默认输入x、y均为正整数，若需要支持负数或0可在此基础上扩展边界逻辑即可。

核心思路 #

全程使用乘法操作替代除法、取模运算，通过递归累计x的幂次乘积，判断是否能匹配目标值y：

• 边界条件1：若当前累计乘积等于y，说明存在符合要求的整数n，返回True
• 边界条件2：若当前累计乘积已经大于y，说明继续乘x只会更大，不可能匹配，返回False
• 递归逻辑：将当前累计乘积乘x，传入下一层递归继续判断
• 特殊边界处理：x=1的场景下，只有y=1时返回True，其余场景均返回False（1的任意次幂都是1）

代码实现 #

def is_power(x, y):
    # 特殊情况处理：x为1的场景
    if x == 1:
        return y == 1
    # 递归辅助函数，current为当前累计的x的幂次结果
    def helper(current):
        if current == y:
            return True
        if current > y:
            return False
        return helper(current * x)
    # 初始传入x^0=1启动递归
    return helper(1)

测试用例验证 #

• 输入is_power(2,16)：返回True，符合示例要求
• 输入is_power(3,27)：返回True
• 输入is_power(5,12)：返回False
• 输入is_power(1,1)：返回True
• 输入is_power(1,5)：返回False

方案合规性说明 #

• 未使用任何math库相关接口
• 未使用%取模运算符
• 全程通过递归实现逻辑，符合要求

内容的提问来源于stack exchange，提问作者PythonAddict