07-简洁至上的斐波那契

1.1.5　简洁至上的斐波那契

还有一种性能更好的做法，即可以用老式的迭代法来解决斐波那契问题，如代码清单1-8所示。

代码清单1-8　fib5.py

def fib5(n: int) -> int:
    if n == 0: return n  # special case
    last: int = 0  # initially set to fib(0)
    next: int = 1  # initially set to fib(1)
    for _ in range(1, n):
        last, next = next, last + next
    return next
if __name__ == "__main__":
    print(fib5(5))
    print(fib5(50))

警告 　 fib5() 中的 for 循环体用到了元组（tuple）解包操作，或许这有点儿过于卖弄了。有些人可能会觉得这是为了简洁而牺牲了可读性，还有些人可能会发现简洁本身就更具可读性，这里的要领就是 last 被设置为 next 的上一个值， next 被设置为 last 的上一个值加上 next 的上一个值。这样在 last 已更新而 next 未更新时，就不用创建临时变量以存储 next 的上一个值了。以这种形式使用元组解包来实现某种变量交换的做法在Python中十分常见。

以上方案中， for 循环体最多会运行 n-1 次。换句话说，这是效率最高的版本。为了计算第20个斐波那契数，这里的 for 循环体只运行了19次，而 fib2() 则需要21891次递归调用。对现实世界中的应用程序而言，这种强烈的反差将会造成巨大的差异！

递归解决方案是反向求解，而迭代解决方案则是正向求解。有时递归是最直观的问题解决方案。例如， fib1() 和 fib2() 的函数体几乎就是原始斐波那契公式的机械式转换。然而直观的递归解决方案也可能伴随着巨大的性能损耗。请记住，能用递归方式求解的问题也都能用迭代方式来求解。