运维开发网

Python例子详细介绍了递归算法

运维开发网 https://www.qedev.com 2022-06-22 21:24 出处:网络
递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。本文将详细为大家介绍Python中的递归算法

递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。本文将详细为大家介绍Python中的递归算法

递归是一种抽象的数学逻辑,可以简单理解为“程序调用自己的算法”。

维基百科对递归的解释是:

递归(英文:Recursion),也译为递归,是指数学和计算机科学中在函数的定义中使用函数本身的方法。递归也常用来描述通过自相似重复事物的过程。

例如,当两个镜像近似平行时,镜像中的嵌套图像以无限递归的形式出现。也可以理解为一个自我复制的过程。

quot通过quot它的意思是通过。Quot意思是返回,先一层一层的传一个方法,然后传到最后一层再返回结果。


比如我排队等核酸检测的时候,前面有100个人。我想问医护人员什么时候下班,就问了前面的那位兄弟。他又问了前面的人,一个一个传过去,最后传给医护人员。他回答说下午六点下班。这句话又传了回来,最后传到我这里。我知道医务人员六点就下班了。

这个过程是一个递归过程,如果quot消息quot本身就是一个方法,然后整个消息流程都在调用自己的方法,最后得到结果。

这和loop不一样,相当于给每个人都戴上耳机,然后有quot中介quot一个一个问,你知道医护人员几点下班吗?你问医护人员,得到的答案,ldquoRdquo告诉我六点下班。

递归本质上就是不断拆解一个大问题,就像剥洋葱一样,最后拆解到最小的层次,就会返回解决问题的结果。


举一个Python中最简单的递归函数的例子,谈谈递归的应用。

我们经常看到函数会调用自己来实现循环运算,比如求阶乘的函数。

整数的阶乘是n*(n-1)*(n-2)*...*3*2*1.

比如下面五行Python代码就可以实现阶乘的计算。

deffact(n):'''n表示要求的数的阶乘'''ifn==1:returnnn=n*fact(n-1)returnnprint(factorial(5))

输出:

120

很多人可能会对这里的计算逻辑感到困惑,为什么事实函数会调用自己,最后得到结果。

我们可以根据数理逻辑推导出:

整数的阶乘是: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)


有没有一个事实方法可以对每一个数都调用,最后调用n=1时,返回结果n的阶乘?


上图可以看到,递归函数会一层一层向下调用,最后当n=1时,结果会向上返回。

这就是递归的整个过程。如果我们给递归下一个准确的定义,可以概括为以下三点:

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...

这个序列从第三项开始,每一项都等于前两项之和。

递归定义如下:F(0)=0,F(1)=1,F(n)= F(n-1)+F(n-2)(nge;2、乳酸链球菌素;N*)

在Python中,我们可以用递归函数来实现斐波那契数列:

# 1,1,2,3,5,8,13,21,34,55,试判断数列第12个数是哪个?deffab(n):'''n为斐波那契数列'''ifnlt;=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时命题成立。0对于一般序列取0或1的值,但也有特殊情况;

(2)假设当n = k(kge;0,k为自然数),证明n=k+1时命题也成立。

综合(1)(2),对于所有自然数n(ge;0),命题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]lt;n:print('向右侧找!')returndichotomy(mid,max,d,n)elifd[mid]gt;n:print('向左侧找!')returndichotomy(min,mid,d,n)else:print('找到了%s'%d[mid])returnres=dichotomy(0,len(data),data,222)print(res)

一个大人物曾经说过:迭代是人,递归是神。

人类理解迭代,上帝理解递归。

可见递归是一种非常神奇的算法。它的神奇之处在于允许用户用有限的语句描述无限的物体。

当然,人无完人,递归也有缺点。它通常效率很低,并且会导致调用堆栈溢出。

因为递归不断调用自己的函数,产生大量的变量,而栈空之间的容量是有限的,循环太多会效率低下,甚至导致调用栈溢出。

以上是Python例子讲解递归算法的详细内容。更多关于Python递归算法的信息

0

精彩评论

暂无评论...
验证码 换一张
取 消