1 什么是递归？
什么是递归？晦涩难懂而又有学术气息的解释网上到处都有。今天就为大家带来一个‘船新版本’。
相信不少人在各种社交APP上都见过‘禁止套娃’的评论，而什么是套娃呢？套娃其实是俄罗斯是特产的木制玩具，一般由多个相同图案的空心木娃娃一个套一个的组成，一般在六个以上。由此 ‘套娃’这个梗的意思也就清晰了：在各种社交网站或视频下方评论区跟人争论时使用重复类似的语言。
图1 递归
有个笑话是这样的：
记者：你放羊为了什么?
放羊娃：赚钱
记者：你赚钱为了什么?
放羊娃：娶媳妇
记者：你娶媳妇为了什么?
放羊娃：生娃
记者：生了娃干什么
放羊娃：放羊。
看了上面的例子，再结合递归的‘调用函数本身’，就理解了递归的含义。通俗讲就是 ‘为所欲为’ 之 ‘为所欲为’ 之 ‘为所欲为’ ……
2 递归全排列
在明白了递归含义后，就来做一个小小的实践：用代码输出[1,2,3,4]数列的全部排列情况（全排列）
思路一
按照数学题思路：
第一个数有4种情况（1，2，3，4），第二个数有3种（除开第一个数），第三个数有2种（除开第一个数和第二个数），第四个数有1种（剩下的数）
因此套用4层循环就可以解决。但是如果不知道列表的长度，此方法就不成立。
思路二
既然理解了递归，就用递归的方法。可以认为是以n1（依次遍历列表）为头部，加上[n2, n3,n4 ,……nn]的全排列，而[n2,n3 ,n4 ,……nn]的全排列可以看成以为头部，加上[n3,n4 ,……nn]的全排列……剩下的就是‘套娃’了，一直套到列表长度为1。
步骤
1.先定义full_array函数，并设置递归结束条件（即列表长度为1时）；
def full_array(List): if len(List)==1: return [List] |
2.遍历列表作为头部，并生成下一个 ‘去头部的列表’ ；
for i in range(len(List)): array=List[:i]+List[i+1:] |
3.对递归后的‘去头部列表’遍历，并与前面所删除的部分相加。
for i in range(len(List)): array=List[:i]+List[i+1:] for ii in full_array(array): Mid=[List[i]]+ii Result.append(Mid) |
完整代码：
def full_array(List): Result=[] if len(List)==1: return [List] else: for i in range(len(List)): array=List[:i]+List[i+1:] for ii in full_array(array): Mid=[List[i]]+ii Result.append(Mid) return Result print(full_array([1,2,3])) |
3 总结
递归就是‘套娃’，一层套一层，但必须设置一个结束条件，就像‘套娃’一定会打开最后一个，递归也必须有最后一层，防止无线递归。而一般也规定了递归最大深度，一旦超过栈就会溢出。递归对不同的问题，使用的位置也不同，因此应该学会递归的思想，而不是狭隘地认为自己仅会阶乘运算，就算得上掌握了递归算法。
