LeetCode 326：判断是否为3的幂递归解法遇递归深度超限错误求助

问题背景 #

LeetCode 326题要求判断给定整数是否是3的幂次方，以下是提交的代码及遇到的错误：

提交代码 #

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        print(n)
        if n % 3 == 0:
            if n == 3:
                return True 
            return self.isPowerOfThree(n/3)
        else: return False

触发错误 #

运行时出现递归错误：

RecursionError: maximum recursion depth exceeded while getting the str of an object
中文翻译：递归错误：获取对象字符串时超出最大递归深度

错误原因分析 #

1. 未处理非正整数输入：当n≤0时，比如n=0，0%3==0会成立，进而递归调用isPowerOfThree(0/3)即isPowerOfThree(0)，陷入无限递归，最终导致栈溢出。
2. 除法返回浮点数：Python中n/3返回浮点数（如9/3=3.0），此时判断n==3会不成立，继续递归调用isPowerOfThree(3.0/3)即isPowerOfThree(1.0)，虽然最终会返回False，但如果输入是类似3.0的情况，会继续递归，增加不必要的调用次数，极端情况也会触发栈溢出。
3. 终止条件不完整：仅判断n==3时返回True，但忽略了3^0=1的情况，1也是3的幂。

修复后的代码 #

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        # 非正整数直接排除
        if n <= 0:
            return False
        # 递归终止条件：n为1时说明是3的幂
        if n == 1:
            return True
        # 能被3整除则继续递归，用整数除法保证类型为整数
        if n % 3 == 0:
            return self.isPowerOfThree(n // 3)
        # 不能被3整除则不是3的幂
        return False

修复逻辑说明 #

• 先过滤所有非正整数，这些数值不可能是3的幂；
• 当n等于1时，直接返回True（对应3^0的情况）；
• 若n能被3整除，用整数除法//将n缩小为原来的1/3，继续递归判断；
• 若n不能被3整除，直接返回False。

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