使用递归计算数字总和的java程序

Question

假设 n = 4。使用递归，我想返回：

1 1 1 1
1 1 2
1 3
2 1 1
2 2
3 1
4

基本上，我想采用数字n并通过组合数字1,2,3和4创建所有可能的变化，当sum == n时需要这些变化。

这是我的第一个想法，但它给了我以下错误信息：

线程“main”中的异常java.lang.StackOverflowError

public static void test_2(String path, int sum, int n){
    if(sum == n){
        System.out.println(path);
    } else {
        test_2(path+"1 ", sum + 1, n);
        test_2(path+"2 ", sum + 2, n);
        test_2(path+"3 ", sum + 1, n);
        test_2(path+"4 ", sum + 2, n);
    }
}

- juku

---

1 2 1 怎么样？你不想要它，还是只是忘了它？ - RaminS

我错过了那个，抱歉。 - juku

因为询问作业（大概）并提供自己的代码而被点赞。很高兴有些人知道如何在这里提问。 - sinclair

Answer 1

主要问题在于当sum != n时，你总是在递归。当和大于n时，你永远不会停止，因此出现了StackOverflowError。这意味着我们需要添加一个检查并在和变得更大时终止：

public static void test_2(String path, int sum, int n) {
    if (sum == n) {
        System.out.println(path);
    } else if (sum < n) { // <-- only recurse if the sum is less than the target
        test_2(path+"1 ", sum + 1, n);
        test_2(path+"2 ", sum + 2, n);
        test_2(path+"3 ", sum + 3, n);
        test_2(path+"4 ", sum + 4, n);
    }
}

作为一个附注，在你的最后两次调用中，你写的是1和2而不是3和4，但这可能只是个笔误。

调用test_2("", 0, 4)的输出结果：

1 1 1 1 
1 1 2 
1 2 1 
1 3 
2 1 1 
2 2 
3 1 
4 

---

但请注意，您当前的代码不太灵活：如果您给n赋值大于4的值，它将无法工作。我建议您进行一些重构。

- Tunaki