递归函数

在python中，函数内部可以调用其他函数，也可以调用函数自身，这种函数内部调用自身的函数我们称为递归函数。 举个例子，阶乘(factorial)的计算：n! = 1*2*3*...*n

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)

factorial(n)就是一个递归函数，试试运行：

>>> factorial(1)
1
>>> factorial(5)
120
>>> factorial(10)
3628800

分析factorial(5)计算过程

===> 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
===> 120

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。