Python 实现尾调用优化

Python 实现尾调用优化，可以通过递归的形式把许多函数简洁明了地表达出来，其中最典型的例子是factorial()。
用Python的递归形式表示如下：

对应的Python实现如下：

def fact(n: int) -> int:
    if n == 0: return 1
    else: return n * fact(n - 1)

该实现的主要优点是简洁，但受制于Python的递归嵌套数量限制，无法进行超过fact(997)的计算。1000!有2568位数，超过了浮点数的最大值。在某些系统中这个上限是 10^{300}。编程实践中，经常使用log gamma函数处理过大的浮点数。

该函数是典型的尾递归形式，函数体的最后一个表达式是对使用了新参数的自身的调用。优化编译器能用循环代替函数调用栈，从而大幅提高计算速度。
由于Python没有优化编译器，所以必须考虑对它们进行优化。这里，函数从n向n-1变化，因此可以构造一个序列，通过归约计算乘积。

如果不考虑纯粹的函数式处理，可以定义如下所示的命令式计算流程：

def facti(n: int) -> int:
    if n == 0: return 1
    f = 1
    for i in range(2, n):
        f = f * i
    return f

此版本的实现能进行高于1000!的计算（例如2000!有5733位数）。它不是纯粹的函数式，我们用有状态的循环优化了尾递归，其中的i变量用于保存计算过程的状态。

总的说来，由于不能自动进行尾调用优化，在用Python编程时只能用这种方法。但有些情况下，这样的优化其实没有益处，下面会详述。