用程序算出约瑟夫环递归的时间复杂度

约瑟夫环（Josephus Problem）是一个经典的计算机科学问题，描述的是在一群按照特定顺序编号的人中，每隔k个人就杀掉一个，直到剩下最后一个人。该问题可以通过递归算法或迭代方法解决。

对于递归解法，时间复杂度分析如下：

- 最简单的递归情况是当人数n为1时，没有循环，时间复杂度为O(1)。
- 对于一般情况，我们需要对前k-1个人执行递归，然后再对剩余的人（n mod k）执行相同的操作，这是一个递归调用的过程。
- 由于每次递归调用处理的人数都比上一次少k（因为每k人中有一个被淘汰），所以递归深度接近 n / k（向下取整），但每次递归操作需要常数时间。
- 因此，总的递归时间复杂度可以用一个等比数列的和来近似，即T(n) ≈ T(n-k) + O(1)，这是一个指数级别的递归，具体来说是O(log n)级别的，因为每次递归规模减半。