2.13.5　递归

从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚。有一天，老和尚给小和尚讲故事：“从前有座山，山上有座庙……”

这个古老的故事里蕴含着一个现代的编程思想：递归（recursion）。递归是循环的一种，它的表现形式是函数调用自身。来看以下最简单的递归调用。

def func1():
    # do something...

    # call itself
    func1()

如果只是简单重复地无限次调用自身，程序会把内存耗尽。实际的应用中，递归函数是在一定条件下才调用自身，当这个条件不满足的时候，递归就会终止。

我们已经知道如何用while循环来计算阶乘，接下来，我们来看如何用递归来实现。自然数n的阶乘写作n!，根据阶乘的特性，我们可以知道n!=n×(n–1)!。

用Python代码表达如下。

def factorial(n):
    if n in [0, 1]:
        return 1

    return n * factorial(n-1)
print(factorial(5))

执行结果如下：

120

这个实现逻辑也不够严谨，但是我们可以看到递归的魔力，它的代码非常简洁，运用得当的话，我们可以写出简单优雅的代码。