6.6 递归函数

在函数内部，可以调用其他函数。如果一个函数在内部直接或者间接调用函数自身，这个函数就是递归函数。

例如，我们用fact(n)函数来计算n的阶乘，即

fact(n) = n! = n x (n - 1) x (n - 2) ... x 3 x 2 x 1

根据阶乘的特点，可以得出这个结果：

fact(n) = n x fact(n - 1)

依此类推：

fact(n - 1) = (n - 1) x fact(n - 1 - 1)

直到：

fact(2) = 2 x fact(2 - 1)

这里fact(1)的值确定之后，就可以逐级算出每一个fact(n - 1)，直到最后的fact(n)，这就是递归函数的思维。

上面的函数可以写成：6.14-递归阶乘.py

# 使用递归函数求阶乘


def fact(n):
    if n == 1:
        res = 1
    else:
        res = n * fact(n - 1)
    return res


print(fact(5))

执行结果为：

120

计算fact(5)时，可以根据函数定义得到计算过程如下：

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

在还没有求出fact(1)的时候，前面的fact(5), fact(4)等函数的调用都没有返回，等在那里，等待fact(n - 1)的结果回来，好计算本次函数的返回值n*fact(n - 1)，直到fact(1)返回了确定的值1，然后逐级的fact(2)有了结果，然后fact(3)也有了结果，最后fact(5)也返回了确定的结果值，于是递归函数计算出了结果。可以使用断点调试的方法查看函数递归调用的情况。

于是在逐级的等待中，fact(5), fact(4)等函数没有返回，没有返回时的函数，是放在一个栈的数据结构中的，调用结束时，从栈中删除。由于递归函数在执行过程中，前面n - 1个函数都没有返回，所以都在栈中堆积。栈的大小有限，如果超出了范围，就会导致栈溢出。所以递归函数的调用次数不能过多。