Python 尾递归优化

Python 尾递归优化，前面介绍了如何将简单的递归优化为for循环。以如下阶乘的简单递归定义为例：

优化递归的通用方法如下。

• 设计递归。这意味着可以测试基本情形和简单函数形式的递归情形，尽管慢但结果是正确的。简单定义如下：

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

• 如果递归的最后有一个简单的调用，则用for循环替代递归，其定义如下：

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

当递归出现在一个简单函数的最后，则将它描述为尾调用优化。许多编译器会将其优化成一个循环。Python没有优化编译器，不会进行这种尾调用转换。

这种模式很常用。执行尾调用优化可以提升性能，并突破可执行递归数量的上限。

在进行任何优化前，函数必须能正常运作。对此，一个简单的doctest字符串通常就足够了。可以对阶乘函数做如下注释：

def fact(n: int) -> int:
    """Recursive Factorial
    >>> fact(0)
    1
    >>> fact(1)
    1
    >>> fact(7)
    5040
    """
    if n == 0: return 1
    else: return n*fact(n-1)

这样就添加了两个边缘情况：显式的基本情形和基本情形后的第一项。还添加了一个涉及多次迭代的项，让我们得以调整代码。

当有更复杂的函数组合时，可能需要执行以下命令：

binom_example = """
>>> binom = Binomial()
>>> binom(52, 5)
2598960
"""

__test__ = {
    "binom_example": binom_example,
}

函数doctest.testmod()使用了变量__test__。字典中所有和变量__test__相关联的值都用于了doctest字符串。这是测试复合函数特性的一种简便方法。由于它测试了多个软件组件的集成性，因此也称其为集成测试。

一组可用的测试代码会利于优化，并便于确认优化的正确性。下面是一句描述优化的名言：

“让程序错上加错并不是罪。” ——Jon Bentley

这句话出自《编程珠玑（续）》一书的“计算机科学箴言集”章。重要的是应该只优化正确的代码。