41个人排成一个圆圈，从第1个人开始报数（从1开始），每次报数为3的人自杀，然后再由下一个人重新报数，直到最后只剩下两个活着的人为止。请问，你应该站在哪里才能活着？

让我们把这个问题先放一放，先来看看什么是递归？知乎上关于这个问题点赞最高的回答是：「不宜公开讨论的政治内容」的定义和范畴本身也属于「不宜公开讨论的政治内容」。

不好理解？继续往下看，来看看这个（小李子，盗梦空间）。你在看镜中的自己，镜中的自己也在看镜中的自己......。

或者这个，电脑显示屏上显示的电脑的显示屏上显示的电脑的显示屏上......有一台电脑。

还是不好理解？再来看看这个，相信你小时候一定听过这样一个故事：从前有座山，山里有座庙，庙里有个老和尚在讲故事，讲的什么故事？从前有座山，山里有座庙，庙里有座老和尚在讲故事，讲的什么故事？从前有座山，山里有座庙，庙里有座老和尚在讲故事，讲的什么故事？......

没错，这就是递归，一种比较常见的编程技巧，即程序自己调用自己。

用递归计算阶乘

让我们来看一个简单的例子，求5的阶乘（factorial）。我们知道5！=5×4×3×2×1=120

【普通方法】

factorial = 1

for i in range(1,6):

factorial *= i

print(factorial)

>>> 120

【递归方法】

def factorial(n):

if n == 1:

return 1

else:

return n*factorial(n-1)

print(factorial(5))

>>> 120

递归函数factorial(5)第1次执行时，由于n=5，所以返回5*factorial(4)，因此递归函数再次被调用执行factorial(4)，依次递推，最后一次n=1，返回1。即：

第1次：factorial(5)第2次：5*factorial(4)第3次：5*4*factorial(3)第4次：5*4*3*factorial(2)第5次：5*4*3*2*factorial(1)第6次：5*4*3*2*1输出>>> 120

经典的约瑟夫问题

约瑟夫问题，又称约瑟夫环，丢手绢问题等。

据说著名犹太历史学家约瑟夫（Josephus）亲历过这样一件事，罗马人占领乔塔帕特后，41个犹太人（包括约瑟夫和他的朋友）躲到一个山洞里，他们决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式。41个人排成一个圆圈，从第1个人开始报数，每次报数为3的人自杀，然后再由下一个重新报数，直到最后只剩下两个活着的人为止（注意：这和报到3的倍数自杀有所不同）。

简单的说，41个人排成一列：

第1步：前两名站到队尾去。

第2步：第三名残忍自杀。

第3步：新队列的前两名（即原来的四五名）站到队尾去。

第4步：第三名残忍自杀。

...

依次循环。

最后，谁活着？

似乎感觉很复杂，没有头绪，但是如果用递归的方法来运算，问题将会变得简单，只需要短短7行代码即可搞定。

persons = ['1号', '2号', '3号', '4号', '5号', '6号', '7号', '8号', '9号', '10号', '11号', '12号', '13号', '14号', '15号', '16号', '17号', '18号', '19号', '20号', '21号', '22号', '23号', '24号', '25号', '26号', '27号', '28号', '29号', '30号', '31号', '32号', '33号', '34号', '35号', '36号', '37号', '38号', '39号', '40号', '41号']def kill(persons): if len(persons) < 3: return(persons) else: new_persons = persons[3:] + persons[:2] return kill(new_persons)alive_persons = kill(persons)print(alive_persons)>>> ['16号', '31号']

也就是说，如果你站在16号位置和31号位置就不会被杀，但这不是幸运，而是智慧。

persons = persons[3:] + persons[:2]上面这行代码的含义是将原列表persons的第4个元素（编号为3，计算机中编号从0开始，详情点击《

究竟是为什么Python的索引要从0开始？？？

》）到最后一个元素以及原列表persons的前2个元素组成一个新的列表new_persons（即删除第3个元素），然后再次调用函数kill(persons)。

如果你想知道每次被杀人的顺序，可以加一行代码，这样每次就会打印出当次自杀的人。

print(persons[2])

new_persons = persons[3:] + persons[:2]