Python中递归算法怎么用
Python中递归算法怎么用
小编给大家分享一下Python中递归算法怎么用,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
递归是一种较为抽象的数学逻辑,可以简单的理解为「程序调用自身的算法」。
维基百科对递归的解释是:
递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。
例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
"递"是传递的意思,"归"是归还的意思,先把一个方法一层层传递下去,然后传递到最后一层再把结果归还回来。
比方说我排队做核酸检测,前面有100个人,我想问下医务人员几点下班,于是问了我前面那兄弟,他又问了他前面的人,一个个传递下去,最终传递到了医务人员那里,回话说下午六点下班。这句话又往回传,最终到了我这里,我知道了医务人员六点下班。
这个过程就是一个递归过程,如果说"传话"本身是一种方法,那这整个传话过程就是在调用自身方法,最终获得了结果。
这和循环不一样,循环相当于给所有人都所有人都戴了耳机,然后有"中介"挨个去问你知道医务人员几点下班吗,等问到医务人员的时候,得到答案,“中介”告诉我六点下班。
实质上,递归就是把一个大问题不断拆解,像剥洋葱一样,最终拆解到最小层面,会返回解题结果。
用Python举一个最简单的递归函数例子,讲一讲什么是递归的应用。
我们经常会看到函数会调用自身来实现循环操作,比如求阶乘的函数。
整数n的阶乘即n*(n-1)*(n-2)*...*3*2*1
如下面5行Python代码,就能实现阶乘的计算
deffact(n):'''n表示要求的数的阶乘'''ifn==1:returnnn=n*fact(n-1)returnnprint(factorial(5))
输出:
120
很多人可能困惑这里面的计算逻辑,为什么fact函数中调用了自身,最终能得到结果。
我们可以按照数学逻辑进行推演:
整数n的阶乘是:fact(n) = n*(n-1)*...*3*2*1
整数n-1的阶乘是:fact(n-1) = (n-1)*(n-2)*...*3*2*1
所以可以推断fact(n) = n*fact(n-1)
这里是不是一种 fact方法可以为每个数所调用,最终调用到了n=1的时候,就返回结果n的阶乘。
大家看上图,递归函数会一层层往下调用,最终到n=1的时候,往上返回结果。
这就是递归的全过程,如果我们给递归下一个准确的定义,可以概括为以下3点:
1、至少有一个明确的递归结束条件;
2、给出递归终止时的处理办法;
3、每次进入更深一层递归时,问题规模(计算量)相比上次递归都应有所减少
以上面代码为例:
deffactorial(n):'''n表示要求的数的阶乘'''ifn==1:#1、明确递归终止条件;returnn#2、递归终止时的处理办法n=n*factorial(n-1)#递去returnn#归来
除了常见的阶乘案例,还有斐波那契数列,也是递归的经典用法。
斐波那契数列:1,1,2,3,5,8,13,21,34,55,89...
这个数列从第3项开始,每一项都等于前两项之和。
它以如下被以递推的方法定义:F(0)=0,F(1)=1,F(n)=F(n - 1)+F(n - 2)(n≥ 2,n∈ N*)
在Python中,我们可以使用递归函数的方式去实现斐波那契数列:
#1,1,2,3,5,8,13,21,34,55,试判断数列第12个数是哪个?deffab(n):'''n为斐波那契数列'''ifn<=2:v=1returnvv=fab(n-1)+fab(n-2)returnvprint(fab(12))
使用数学方法进行推导:
fab(0) = 0(初始值)
fab(1) = 1(初始值)
对所有大于1的整数n:fab(n) = fab(n-1)+ fab(n-2)(递归定义)
其实以上两个递归的案例都可以用数学归纳法来解释,就是高中数学的知识。
一般地,证明一个与自然数n有关的命题P(n),有如下步骤:
(1)证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1,但也有特殊情况;
(2)假设当n=k(k≥n0,k为自然数)时命题成立,证明当n=k+1时命题也成立。
综合(1)(2),对一切自然数n(≥n0),命题P(n)都成立。
除了数学的解释,之前也看到有人对递归更加形象的解释:
1、我们已经完成了吗?如果完成了,返回结果。如果没有这样的终止条件,递归将会永远地继续下去。
2、如果没有,则简化问题,解决较容易的问题,并将结果组装成原始问题的解决办法。然后返回该解决办法。
哈哈,到这里大家是不是对递归有了一个更加深刻的认识。
如果还不清楚,没关系,这里还有更多的递归案例,用Python来实现,可以说非常简洁。
「最大公因数:」
defgcd(m,n):ifn==0:returnmelse:returngcd(n,m%n)
「从 1 到 n 的数字之和:」
defsumnums(n):ifn==1:return1returnn+sumnums(n-1)print(sumnums(3))
「字符串倒序:」
defreverse(string):iflen(string)==0:returnstringelse:returnreverse(string[1:])+string[0]reverseme='我是帅哥'print(reverse(reverseme))
「汉诺塔问题:」
deftowerOfHanoi(numrings,from_pole,to_pole,aux_pole):ifnumrings==1:print('Movering1from',from_pole,'poleto',to_pole,'pole')returntowerOfHanoi(numrings-1,from_pole,aux_pole,to_pole)print('Movering',numrings,'from',from_pole,'poleto',to_pole,'pole')towerOfHanoi(numrings-1,aux_pole,to_pole,from_pole)numrings=2towerOfHanoi(numrings,'Left','Right','Middle')
「二分法找有序列表指定值:」
data=[1,3,6,13,56,123,345,1024,3223,6688]defdichotomy(min,max,d,n):'''min表示有序列表头部索引max表示有序列表尾部索引d表示有序列表n表示需要寻找的元素'''mid=(min+max)//2ifmid==0:return'None'elifd[mid]<n:print('向右侧找!')returndichotomy(mid,max,d,n)elifd[mid]>n:print('向左侧找!')returndichotomy(min,mid,d,n)else:print('找到了%s'%d[mid])returnres=dichotomy(0,len(data),data,222)print(res)
有位大佬说过:To Iterate is Human, to Recurse, Divine.
中文译为:人理解迭代,神理解递归。
可见递归是非常神奇的算法,它的神奇之处在于它允许用户用有限的语句描述无限的对象。
当然人无完人,递归也是有缺点的,它一般效率较低,且会导致调用栈溢出。
因为递归不断调用自身函数,且产生大量变量,而栈空间的容量是有限的,循环太多就会效率低下,甚至导致调用栈溢出
以上是“Python中递归算法怎么用”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注恰卡编程网行业资讯频道!
推荐阅读
-
python(中无效的十进制怎么解决 python怎么转换进制)
python怎么转换进制?Python执行二进制转换:1.十进制到二进制(bin)首先,让让我们看看如何将十进制转换成二进制。我...
-
python怎么清除完全相同的行(python splte如何分隔有多个相同符号的str)
pythonsplte如何分隔有多个相同符号的str?str你的string内容str_(相同的符号)执行完了以后再在相同符号的...
-
python(编程控制电脑关机 如何控制电脑关机)
如何控制电脑关机?可以在电脑的运行窗口中输入输入公式,给电脑可以设置自动关机。1.按开快捷键winr然后打开运行窗口。2.在运行窗...
-
python中的特殊标识符(python 中 标识符中可以有逗号吗)
python中标识符中可以有逗号吗?在python语言中合法的标识符是字母、数字以及_,所以我合法的标识符中肯定不能有逗号if...
-
python(excel 提取数据写入新表 python导入excel数据找不到工作簿)
python导入excel数据找不到工作簿?我可以导入数据后找不到工作,不是因为他的工作没有被转移。什么软件可提取并合并Exce...
-
python中字典定义的四种方法(python global关键字的用法详解)
pythonglobal关键字的用法详解?global标志实际上是目的是提示python讲解器,说被其修饰的变量是全局变量。这样...
-
python(array用法 python如何对两个数组做差处理)
python如何对两个数组做差处理?Python中的列表中的元素肯定不能真接相加,减。t最佳的位置的是将列表装换成Python中的...
-
python多行注释符号怎么表示
python多行注释符号怎么表示这篇文章主要介绍“python多行...
-
python支持的操作系统是什么
python支持的操作系统是什么这篇文章主要介绍“python支持...
-
python如何判断列表为空
python如何判断列表为空这篇文章主要介绍“python如何判断...