递归终止条件顺序不同致3的幂和判定结果差异原因咨询

需求说明 #

编写布尔类型方法，传入大于0的正整数n，判断n是否可以表示为若干个3的幂次之和，且每个幂次在求和表达式中最多仅能出现一次。

• 正确示例：输入n=37返回true，对应等式为3^0 + 3^2 + 3^3 = 37
• 错误示例：输入n=38返回false

问题现象 #

递归实现该方法时，仅当把终止条件n==0写在p3i>n || n<0判断之前时，运行结果才正确；调换两个条件的书写顺序后输出结果错误。
两个版本的实现代码如下：

public static boolean sumPower3(int num)
{ 
    return sumPower3(num,0); 
}
// 版本1（输出错误，输入37返回false）
private static boolean sumPower3(int n,int i)
{
    int p3i = (int)Math.pow(3,i);
    if(p3i>n || n<0){return false;}
    if(n==0){return true;}
    return sumPower3(n-p3i,i+1) || sumPower3(n,i+1);
}
// 版本2（输出正确，输入37返回true）
private static boolean sumPower3(int n,int i)
{
    int p3i = (int)Math.pow(3,i);
    if(n==0){return true;}
    if(p3i>n || n<0){return false;}
    return sumPower3(n-p3i,i+1) || sumPower3(n,i+1);
}

原因分析 #

问题本质是版本1的判断顺序错把合法的成功终止场景拦截成了失败：

• 递归的核心逻辑是每一层做两个选择：选当前的3^i加入求和（传入n-p3i到下一层），或者不选当前的3^i（传入原n到下一层），逐层把幂次i加1。当某层传入的剩余待凑值n=0时，说明之前选的幂次刚好凑够原数，是唯一的成功终止条件，必须返回true。
• 版本1先计算当前i对应的p3i，再判断p3i>n || n<0。当递归走到成功场景、传入n=0时，不管当前i值是多少，p3i最小为3^0=1，必然满足p3i>n（1>0），此时方法会直接返回false，根本执行不到后面的n==0判断，所有本该返回成功的路径全部被错判为失败，结果自然错误。
• 版本2把n==0的判断放在最优先位置，只要检测到剩余值为0就立刻返回成功，不会再执行后续的幂次计算和越界判断，能正确捕获所有合法的成功终止场景，运行结果正确。

写递归终止条件的通用注意点：代表「任务完成/执行成功」的判断优先级，必须高于「越界/执行失败」的判断，否则成功路径会被失败分支提前截断。

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