n people stand in a circle. Counting starts at person 1, and every k-th person is eliminated until one remains. Who survives?
Simulating with a list costs O(n²). The recurrence is elegant: after the first elimination, the remaining circle is a Josephus problem of size n − 1, just renumbered to start after the eliminated person:
J(1) = 0
J(n) = (J(n − 1) + k) mod n (0-indexed)
Add 1 at the end for 1-based numbering. Re-labelling a smaller instance so it matches the original is the heart of many recursive solutions.