n选择Java中的k递归问题

Question

我是Java新手，正在尝试用Java编写n choose k。然而，我遇到了一个问题。

public class App {
public static void main(String[] args) throws Exception {
    int n = 3;
    int k = 2;
    int result = combRecursion(n, k);
    System.out.println(result);
}

private static int combRecursion(int n, int k) {
    if (k == 0) {
        return 1;
    } else {
        return (combRecursion(n - 1, k - 1) + combRecursion(n - 1, k));
    }
}

输出：这方面的许多迭代：

        at App.combRecursion(App.java:14)

如果有人能帮忙，我将不胜感激。

Answer 1

在递归方法中，您已经编写了k参数，它将决定结束递归的基本情况。

基本case只检查ks值，右递归调用继续进行递归调用，其中k保持不变，其嵌套的递归调用反过来也会做同样的事情，无休止地生成右递归调用。

那个递归调用给你一个StackOverflow Error。

您应该将其改写为：

int choose(int n, int k) {
    if (k == 0) return 1;
    return (n * choose(n - 1, k - 1)) / k;
}

Answer 2

您的基本情况应该包括n==k | | k==0，以便正确实现“n选择k”。这样，两个调用最终都会终止（即使您当前的实现效率很低，因为它具有指数运行时）。更好的实现应该使用公式n/k/（n-k） 或在线性时间内运行的乘法公式：

int factorial(int n) {
    int res = 1;
    for (; n > 1; n--) {
        res *= n;
    }
    return res
}
int choose(int n, int k) {
    return factorial(n)/factorial(k)/factorial(n-k);
}

进一步优化这是留给读者的练习（提示：单个for循环就足够了）。