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

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