n choose k recursion issue in Java-CodePudding

I am new to Java and am trying to write n choose k in java. However, I run into a problem.

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));
    }
}

Output: many iterations of this:

        at App.combRecursion(App.java:14)

Would appreciate it if anyone can help.

CodePudding user response：

Your base case ought to include both n == k || k == 0 for "n choose k" to be implemented correctly. That way, both calls will eventually terminate (even though your current implementation is rather inefficient as it has exponential runtime). A better implementation would use the formula n!/k!/(n-k)! or the multiplicative formula to run in linear time:

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);
}

further optimizing this is left as an exercise to the reader (hint: a single for loop suffices).

CodePudding user response：

Within your recursive method you've written that k is the parameter which will determine the base case to end the recursion.

Your base case only checks ks value and your right recursive call keeps making a recursive invocation where k stays the same and its nested recursive invocations will do as much in turn, endlessly producing right recursive calls with no end.

That recursive call is what is giving you a StackOverflowError.

You should rewrite it as:

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