Python |
您所在的位置:网站首页 › 套娃有几层 › Python |
本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。 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 总结 递归就是‘套娃’,一层套一层,但必须设置一个结束条件,就像‘套娃’一定会打开最后一个,递归也必须有最后一层,防止无线递归。而一般也规定了递归最大深度,一旦超过栈就会溢出。递归对不同的问题,使用的位置也不同,因此应该学会递归的思想,而不是狭隘地认为自己仅会阶乘运算,就算得上掌握了递归算法。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |