Implementing N choose K recursively in Java

Question

I am new to Java and am I trying to implement a recursive method for finding "n choose k".

However, I've 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 repetitions of this line:

at App.combRecursion(App.java:14)

You forgot n = k case https://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_formula — akuzminykh, May 01 '22 at 14:26
@AlexanderIvanchenko FYI: "n choose k" specifically refers to binomial coefficient. So, when you edited the title, you basically made it less specific. — akuzminykh, May 02 '22 at 03:32
@akuzminykh Thanks, amended the title and the description. If it still doesn't look smooth, please edit the question. — Alexander Ivanchenko, May 03 '22 at 21:18

Alexander Ivanchenko · Answer 1 · 2022-05-03T21:36:41.440

It's possible to pick k items from the set of n items only if n is greater or equal to k.

You need to cut off fruitless branches of recursion spawn by the call combRecursion(n - 1, k) which doesn't reduce the number of item in the sample.

When you need to create a recursive method, it should always contain two parts:

Base case - that represents a set of edge-cases, trivial scenarios for which the result is known in advance. If the recursive method hits the base case (parameters passed to the method match one of the conditions of the base case), recursion terminates. In for this task, the base case will represent a situation when the source list was discovered completely and position is equal to its size (invalid index).
Recursive case - a part of a solution where recursive calls are made and where the main logic resides.

Your recursive case is correct: it spawns two recursive branches of execution (one will "pick" the current item, the second will "reject" it).

But in the base case, you've missed the scenario mentioned above, we need to address these situations:

n isn't large enough (k > n), so that is not possible to fetch k item. And the return value will be 0 (or instead of returning a value, you might throw an exception).
k == 0 result should be 1 (it's always possible to take 0 items, and there's only one way to do it - don't pick anything).
When k == n - there's only one way to construct a combination, as @akuzminykh has pointed out. And the return value will be 1

Note that because your goal is to get familiar with the recursion (I'm pretty sure that you're doing it as an exercise) there's no need to mimic the mathematical formula in your solution, use pure logic.

Here is how you can implement it:

private static int combRecursion(int n, int k) {
    if (k > n) return 0;  // base case - impossible to construct a combination
    if (n == k || k == 0) return 1; // base case - a combination was found
    
    // recursive case
    return combRecursion(n - 1, k - 1) + combRecursion(n - 1, k);
}

main() - demo

public static void main(String[] args) {
    System.out.println(combRecursion(3, 2));
    System.out.println(combRecursion(5, 2));
}

Output

3  // pick 2 item from the set of 3 items
10 // pick 2 item from the set of 5 items

"[...] there's no need to mimic the mathematical formula in your solution, use pure logic." -- It's not like the recursive formula for binomial coefficient is illogical. The n = k case, where you return 1, is perfectly logical. There is only one way to pick n from a set of n. Also, covering it reduces the number of calls in some cases; e.g., when n = k = 100, you get not a single recursive call. Your code would do 200 recursive calls. One could consider k > n to be an `IllegalArgumentException` as it is undefined for binomial coefficient, but this is probably opinion-based. — akuzminykh, May 02 '22 at 03:27

Luatic · Answer 2 · 2022-05-01T14:38:27.627

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).

Implementing N choose K recursively in Java

2 Answers2