Recurrence relation in Josephus p‌r‌o‌b‌l‌e‌m

Question

The josephus problem can be solved by the below recursion:

 josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
 josephus(1, k) = 1

How this recurrence relation has been derived?

Answer 1

josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1 ...... (1)

To put it in simple words - starting with the "+1" in the formula. It implies that 1 iteration of the recurrence has already been done. Now, we would be left with n-1 persons/elements. We need to process n-1 elements recursively at intervals of k. But, now, since the last element to be removed was at kth location, we would continue from thereof. Thus, k-1 added. Further, this addition might upset the indexing of the array. Thus %n done to keep the array index within the bounds. Hope it is lucid and elaborate enough :) .