The key understanding made for this decision makes sense to me: the result of josephus(n, k) best not to be perceived as the number surviving by Josephus, but rather as the index of the number that is Josephus surviving. For example, a call to josephus(5, 2) will tell you the index of a person from a ring of five that ends in survival.
Given this intuition, think about how Josephus works by looking at a concrete example. Suppose we want to know josephus(n, 2) . You can imagine that we have Russian people who are lined up like this:
1 2 3 4 5 ... n
The first thing that happens is that person 1 kills person 2, as shown here:
1 X 3 4 5 ... n
Now we have a subtask of the following type: there are n-1 people left, every other person will be killed, and the first person who will stab is person 3. In another word, we are left with a ring of people in the form:
3 4 5 ... n 1
with k = 2. Now imagine that we are making a recursive call to josephus(n - 1, 2) , since we have n - 1 people. This will return the index of the one who survives in line n - 1 people. Given that we have an index of the person who will survive, and we also know who is the eldest, we can determine which one will remain. Here's how we do it.
The senior in this line is the person who comes immediately after the last person. This will be person 3. The 1-indexed position of the survivor in the ring of four people is given by josephus(n - 1, 2) . Thus, we can go forward josephus(n - 1, 2) - 1 positions, wrapping a ring, if necessary, to get to our final position. In other words, the survivor is determined by the position
(3 + josephus(n - 1, 2) - 1) % n
However, the problem with this above formula. If we really use single-indexing, what happens if the last survivor is in position n? In this case, we accidentally return position 0 as our answer, but we really need position n. As a fix for this, we will use the trick to use the mod to bypass using single indexing: we take the internal quantity (single indexed position) and subtract one to get a position with a zero index. We will change this number to n to get a zero index position wrapped around. Finally, we add back one to get a single indexed position wrapped around. It looks like this:
(3 + josephus(n - 1, 2) - 2) % n + 1
Thus, the 2nd term comes from two independent -1: the first -1 - this is because josephus(n - 1, 2) returns an index with one index, therefore, to step forward in the correct number of positions, we must complete the steps josephus(n - 1, 2) - 1 forward. The second -1 comes from the fact that we are using single indexing rather than zero indexing.
Generalize this to work for any k, not just k = 2. Suppose we want to know josephus(n, k) . In this case, person 1 will kill person k, leaving us with this array:
1 2 3 ... k-1 X k+1 ... n
Now we essentially need to solve the subtask in which the person k + 1 comes first:
k+1 k+2 ... n 1 2 ... k-1
So, we compute josephus(n - 1, k) to get the one-indexed survivor from the ring of k people, and then move forward on these many steps:
(k+1 + josephus(n - 1, k) - 1)
We need to worry about where we wrap, so we need a mod on n:
(k+1 + josephus(n - 1, k) - 1) % n
However, we indexed once, so we need to use the trick of subtracting 1 from the internal value, and then add 1 to the end:
(k+1 + josephus(n - 1, k) - 2) % n + 1
which simplifies to
(k-1 + josephus(n - 1, k)) % n + 1
which is equivalent
(josephus(n - 1, k) + k-1) % n + 1
as in the decision code.
To summarize: the term k-1 comes from the beginning at position k + 1, adding the corresponding amount to josephus(n - 1, k) - 1 , then subtracting it and adding it back to the end to make the correct wrapper.
Hope this helps!