04-基线条件的运用

1.1.2　基线条件的运用

请注意，在运行 fib1() 之前，Python运行环境不会有任何提示有错误存在。避免无限递归由程序员负责，而不由编译器或解释器负责。出现无限递归的原因是尚未指定基线条件（base case）。在递归函数中，基线条件即函数终止运行的时点。

就斐波那契函数而言，天然存在两个基线条件，其形式就是序列最开始的两个特殊数字0和1。0和1都不是由序列的前两个数求和得来的，而是序列最开始的两个特殊数字。那就试着将其设为基线条件吧，具体代码如代码清单1-3所示。

代码清单1-3　fib2.py

def fib2(n: int) -> int:
    if n < 2:  # base case
        return n
    return fib2(n - 2) + fib2(n - 1)  # recursive case

注意 　 斐波那契函数的 fib2() 版本将返回 0 作为第0个数（ fib2(0) ），而不是第一个数，这正符合我们的本意。这在编程时很有意义，因为大家已经习惯了序列从第0个元素开始。

fib2() 能被调用成功并将返回正确的结果。可以用几个较小的数试着调用一下，具体代码如代码清单1-4所示。

代码清单1-4　fib2.py（续）

if __name__ == "__main__":
    print(fib2(5))
    print(fib2(10))

请勿尝试调用 fib2(50) ，因为它永远不会终止运行！每次调用 fib2() 都会再调用两次 fib2() ，方式就是递归调用 fib2(n - 1) 和 fib2(n - 2) （如图1-3所示）。换句话说，这种树状调用结构将呈指数级增长。例如，调用 fib2(4) 将产生如下一整套调用：

fib2(4) -> fib2(3), fib2(2)
fib2(3) -> fib2(2), fib2(1)
fib2(2) -> fib2(1), fib2(0)
fib2(2) -> fib2(1), fib2(0)
fib2(1) -> 1
fib2(1) -> 1
fib2(1) -> 1
fib2(0) -> 0
fib2(0) -> 0

不妨来数一下（如果加入几次打印函数调用即可看明白），仅为了计算第4个元素就需要调用9次 fib2() ！情况会越来越糟糕，计算第5个元素需要调用15次，计算第10个元素需要调用117次，计算第20个元素需要调用21891次。我们应该能改善这种情况。