递归求解硬币组合数遇Stack Overflow错误，如何修正终止条件？

仅使用镍币（nickel，5分）和dime（10分）硬币，凑成n分有多少种方式？（注：原问题中“hundred coins”应为笔误，实际应为凑成100分）

现有代码 #

public class Recurrences {

    public static void main(String[] args){

        System.out.println("C(100) = " + C(100));
        System.out.println("F(47) = " + C(47));
        System.out.println("D(20) = " + C(20));
        System.out.println("U(19) = " + C(19));
    }

    private static long C(int n){
        if(n == 1) {
            return 1; 
        }
        if(n == 2) {
            return 1;
        }
       
        return C(n - 10) + C(n - 5);
        
    }
}

遇到的错误 #

at Recurrences.C(Recurrences.java:19)
at Recurrences.C(Recurrences.java:19)
at Recurrences.C(Recurrences.java:19)
at Recurrences.C(Recurrences.java:19)
at Recurrences.C(Recurrences.java:19)
at Recurrences.C(Recurrences.java:19)
at Recurrences.C(Recurrences.java:19)

问题分析与解决方法 #

1. 栈溢出的核心原因

你的递归没有设置正确的终止条件：

• 原代码中n==1、n==2返回1完全错误，5分和10分硬币根本凑不出1、2分，应该返回0；
• 当n减去5或10后变成负数时，没有终止逻辑，会无限递归调用，最终导致栈溢出。

2. 正确的终止条件

递归的终止逻辑需要符合实际场景：

• 当n == 0：表示刚好凑出目标金额，这是1种有效方式（不用任何硬币）；
• 当n < 0：金额为负，无法用现有硬币凑出，返回0。

3. 修正后的递归代码

public class Recurrences {

    public static void main(String[] args){
        System.out.println("C(100) = " + C(100)); // 输出11
        System.out.println("C(47) = " + C(47));   // 输出0（47不是5的倍数，无法凑出）
        System.out.println("C(20) = " + C(20));   // 输出3（0个10分+4个5分、1个10分+2个5分、2个10分+0个5分）
        System.out.println("C(19) = " + C(19));   // 输出0（19不是5的倍数）
    }

    private static long C(int n){
        // 刚好凑成目标，1种方式
        if(n == 0) {
            return 1;
        }
        // 金额不足，无法凑成
        if(n < 0) {
            return 0;
        }
        // 递归分支：选1个10分硬币的组合数 + 选1个5分硬币的组合数
        return C(n - 10) + C(n - 5);
    }
}

4. 优化方案：避免递归栈溢出（迭代动态规划）

如果计算的n很大（比如1000），递归深度会过高，仍可能触发栈溢出。可以用迭代式动态规划解决：

public class Recurrences {

    public static void main(String[] args){
        System.out.println("C(100) = " + C(100)); // 输出11
        System.out.println("C(47) = " + C(47));   // 输出0
        System.out.println("C(20) = " + C(20));   // 输出3
        System.out.println("C(19) = " + C(19));   // 输出0
    }

    private static long C(int n) {
        // 非5的倍数直接返回0，因为硬币都是5的倍数
        if (n % 5 != 0) {
            return 0;
        }
        // 简化问题：将金额除以5，转化为用1（原5分）和2（原10分）凑m = n/5的组合数
        int m = n / 5;
        long[] dp = new long[m + 1];
        dp[0] = 1; // 凑0的方式只有1种（不用硬币）
        
        for (int i = 1; i <= m; i++) {
            // 选1个"简化单位1"的情况（对应原5分硬币）
            long count5 = (i >= 1) ? dp[i - 1] : 0;
            // 选1个"简化单位2"的情况（对应原10分硬币）
            long count10 = (i >= 2) ? dp[i - 2] : 0;
            dp[i] = count5 + count10;
        }
        return dp[m];
    }
}

这个版本通过迭代计算，避免了递归栈的开销，同时效率更高（没有重复计算子问题）。

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