问题描述：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。

解决方法：最暴力的就是用环形链表，被选中就移除，时间复杂度为 O(n * m)，空间复杂度是 O(n)。

递归是思路是每次我们删除了某一个士兵之后，我们就对这些士兵重新编号，然后我们的难点就是找出删除前和删除后士兵编号的映射关系。

我们定义递归函数 f(n，m) 的返回结果是存活士兵的编号，显然当 n = 1 时，f(n, m) = 1。假如我们能够找出 f(n，m) 和 f(n-1，m) 之间的关系的话，我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

1
2
3
4
5
6
7
8
9
10
11
…
1
...
m - 2
m - 1
m
m + 1
m + 2
...
n
…

进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：

1
2
3
4
5
6
7
8
删除前  ---  删除后
…      ---  …
m - 2  ---  n - 2
m - 1  ---  n - 1
m      ---  无(因为编号被删除了)
m + 1  ---  1(因为下次就从这里报数了)
m + 2  ---  2
…      ---  …

新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1， 2， 3 的节点。

假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为：

1
old = (new + m - 1) % n + 1

注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.
这样，我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了，而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下：

1
2
3
4
int f(int n, int m)
{
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

参考：https://www.iamshuaidi.com/145.html