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

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