Python之递归函数

Python之递归函数

好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。

Python是支持递归函数的。简单地说,一个递归函数就是直接或间接地调用自身的函数,并且要有退出条件。枯燥的概念令人生厌,我们直接来个例子看看递归函数是如何工作的。例如我们对一个数字列表进行求和计算,我们可以使用内置的函数或者自己写一个函数来完成计算工作,接下来我们看看如何使用递归来完成求和运算:

In[1]:defmysum(L):

...:ifnotL:

...:return

...:else:

...:returnL[]+mysum(L[1:])

...:

In[2]:mysum([1,2,3,4,5])

Out[2]:15

如果对上面的函数较为困惑,可以使用函数来打印每次递归时列表的值:

In[3]:defmysum(L):

...:print(L)

...:ifnotL:

...:return

...:else:

...:returnL[]+mysum(L[1:])

...:

In[4]:mysum([1,2,3,4,5])

[1,2,3,4,5]

[2,3,4,5]

[3,4,5]

[4,5]

[5]

[]

Out[4]:15

通过上述的输出可以发现:每次递归时,列表的长度都变短了,直到列表变为空时,递归终止。对于上面的代码,我们可以使用另外一种代码形式来实现,也就是使用三目运算符,然而在Python中是没有三目运算符的,不过可以使用来实现,代码如下:

In[1]:defmysum(L):

...:returnifnotLelseL[]+mysum(L[1:])

...:

In[2]:mysum([1,2,3,4,5])

Out[2]:15

说到递归还有一个阶乘的例子要个大家说说:

In[5]:deffactorial(number):

...:ifnumber

...:return1

...:else:

...:returnnumber*factorial(number-1)

...:

In[6]:foriinrange(11):

...:print("! = ".format(i,factorial(i)))

...:

!=1

1!=1

2!=2

3!=6

4!=24

5!=120

6!=720

7!=5040

8!=40320

9!=362880

10!=3628800

如果计算,可以根据函数定义看到其计算过程:

===>factorial(5)

===>5*factorial(4)

===>5*(4*factorial(3))

===>5*(4*(3*factorial(2)))

===>5*(4*(3*(2*factorial(1))))

===>5*(4*(3*(2*1)))

===>5*(4*(3*2))

===>5*(4*6)

===>5*24

===>120

使用递归函数需要注意防止栈溢出。在计算机中,函数调用是通过栈(stack) 这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函 数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的 次数过多,会导致栈溢出。可以试试factorial(1000):

>>>factorial(1000)

Traceback(mostrecentcalllast):

File"",line1,in

File"",line4,infactorial

...

File"",line4,infactorial

RuntimeError:maximumrecursiondepthexceeded

使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。今天的内容就到这里,明天继续。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20171220G0LNA600?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励