原文链接：https://blog.csdn.net/qq_40692274/article/details/124592025
【前言】本文讨论经典算法问题约瑟夫环问题的递归解法。
一、问题描述
作为算法中的经典问题，约瑟夫环问题自诞生以来有各种各样的变种描述，丢手绢、游戏获胜者、圆圈中最后剩下的数字、点名游戏等等，但都是同样的数学模型和解题思路。为了讨论该问题，现在将其统一描述如下：
0 , 1 , … , n-1 这 n 个数字围成一个圆，从数字 0 开始，每次从这个圆里删除第 m 个数字（删除后从下一个数字开始重新计数）。求这个圆圈里剩下的最后一个数字是多少。
样例
输入：int n = 6, int m = 3
输出：int ret = 0
讲解：
0, 1, 2, 3, 4, 5 从0开始删除第3个数字，012，2退出
0, 1, 3, 4, 5 从3开始删除第3个数字，345，5退出
0, 1, 3, 4 从0开始删除第3个数字，013，3退出
0, 1, 4 从4开始删除第3个数字，401，1退出
0, 4 从4开始删除第3个数字，404，4退出
0是最后剩下的数字
二、递归解法
本文不再讲解 数组模拟 的解法，直接讨论递归法。约定用记号f(n,m)表示n个数、每次删除第m个时该问题的解，例如由上述样例就有f(6,3)=0。
1、思路分析
我们再来仔细推演f(6,3)的计算过程，“ 0, 1, 2, 3, 4, 5 ”在第一轮中有6个数字，删除从0开始的第3个数字“ 2 ”以后剩下“ 0, 1, 3, 4, 5 ”。接着的第二轮中还有5个数字，要从“ 3 ”开始继续删除第3个数字，由于这些数字围成一个圆，我们不妨把“ 0, 1 ”放在“ 3, 4, 5 ”的后面变成“ 3, 4, 5, 0, 1 ”方便计算。
调整位置后，第2轮的f(6,3)不禁我们联想到f(5,3)，f(5,3)第1轮和f(6,3)第2轮同样有5个数字、同样从第1个位置开始删除第3个数字，换言之，他们要删除的元素位置是一样的，不一样的仅仅是位置上的值。只要我们能找到相同位置上值的关系，就能通过f(5,3)求出f(6,3)、f(4,3)求出f(5,3)、f(3,3)求出f(4,3)，直到利用f(1,3)=0回溯。
观察后发现，f(5,3)中的0对应f(6,3)的3、1对应4、2对应5、3对应0、4对应1，也即f(6,3) = ( f(5,3)+3 ) % 6。如果继续列举就会进一步发现：f(5,3) = ( f(4,3)+3 ) % 6、f(4,3) = ( f(3,3)+3 ) % 6…由此我们就找到了f(n,m)的通项公式为
f(n,m) = ( f(n-1,m)+m ) % n 直到f(1,m)=0
利用这个公式，我们可以很容易地使用递归法解决约瑟夫环问题。
2、源代码
private int lastNum(int n, int m)
{
if (n==1)
return 0;
return ( lastNum(n-1,m)+m ) % n;
}
3、复杂度分析
时间复杂度：O(n) 对n个数要计算n次f(n,m)
空间复杂度：O(n) 计算n次f(n,m)时递归n-1次
————————————————