Problem

I’m trying to compute the probability of rolling a certain dice total with an unknown number of dice. Below is a brute force example for 5 dice, hence the 5 loops. I feel like there is a recursive answer here that I can’t put my finger on that would work for different numbers of dice.

```
function computeDiceOdds(dice, desired_result, sides = 6) {
var successes = 0;
for (let a = 1; a <= sides; a++ ) {
for (let b = 1; b <= sides; b++) {
for (let c = 1; c <= sides; c++) {
for (let d = 1; d <= sides; d++) {
for (let e = 1; e <= sides; e++) {
if ((a + b + c + d + e) == desired_result) {
successes++;
}
}
}
}
}
}
return successes.toString() + " / " + Math.pow(sides, dice).toString();
}
console.log(computeDiceOdds(5, 21)); // "540 / 7776"
```

Solution

I feel like there is a recursive answer here that I can’t put my finger on that would work for different numbers of dice.

Sure. Let’s work with an example, let’s say the one in the question: how many ways can we roll 5 dice to get 21.

The answer could be computed as the sum of answers of the following questions:

- How many ways are there to roll 4 dice to reach 20? (first roll was 1)
- How many ways are there to roll 4 dice to reach 19? (first roll was 2)
- …
- How many ways are there to roll 4 dice to reach 15? (first roll was 6)

And each of these questions can be further broken down:

- How many ways are there to roll 3 dice to reach 19? (first roll was 1, 2nd was 1)
- How many ways are there to roll 3 dice to reach 20? (first roll was 1, 2nd was 2)
- …
- How many ways are there to roll 3 dice to reach 9? (first roll was 6, 2nd was 6)

I hope you see how the pattern will reach a point where we are actually able to give an answer, for example:

- How many ways are there to roll 0 dice to reach 0 -> 1 ðŸ™‚
- How many ways are there to roll 0 dice to reach 1 -> 0, not possible to reach non-zero without dice
- How many ways are there to roll 2 dice to reach 0 -> 0, not possible, the remaining rolls will be greater than 0
- …

In other words, the recursive function must first check the terminating condition, as usual. If we know the answer given the input (0 or 1), we return it. Otherwise, we compute the sum of calling the function for each possible path (dice value), with one less dice, and reduced target to reach.