Python 复杂的尾调用优化

Python 复杂的尾调用优化，可以用递归的形式定义斐波那契数列。第 n 个斐波那契数 F_n 的计算公式如下：

将斐波那契数 F_n 定义为其前面两个数的和 F_{n-1}+F_{n-2}:。这是多次递归的典型例子，无法用简单的尾递归优化进行转换。但如果不把它优化成尾递归，计算速度会慢到基本不可用。

下面是个简单的实现：

def fib(n: int) -> int:
    if n == 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

由于是多次递归，当需要计算fib(n)时，必须先算出fib(n - 1)和fib(n - 2)。由于计算fib(n - 1)时重复计算了一次fib(n - 2)，导致斐波那契函数的实际计算增加了一倍。

Python是从左向右依次对表达式求值的，最大可以计算fib(1000)，但实际计算这么大的数需要非常有耐心。

下面改写整个算法，用有状态的变量代替递归。

def fibi(n: int) -> int:
    if n == 0: return 0
    if n == 1: return 1
    f_n2, f_n1 = 1, 1
    for _ in range(3, n+1):
        f_n2, f_n1 = f_n1, f_n2+f_n1
    return f_n1

这里的有状态版本从0向上计算，而不像递归版本从 向下计算，速度会比递归版本快得多。

需要强调的是，对fib()函数的递归优化没有简便方法。为了能用命令式版本代替递归版本，必须结合具体算法，确定所需中间变量的数量。