斐波那契数列

什么是斐波那契数列？

相信对于各位程序员来说，斐波那契数列是个无比熟悉的东西了（递 归 启 蒙），不需要什么多余的介绍。不过出于让文章变得更友好些，还是简单提一下吧。
其实在数学上，斐波那契数列就是以递归的形式定义的：
$$
F_0=0 \
F_1=1 \
F_n=F_{n-1}+F_{n-2}（n \ge 2）
$$
用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。

最先想到的实现！

其实看完上面的三个公式，很快就能把对应的求斐波那契数的函数写出来了。最经典（应该吧）的写法如下：

def fib0(n: int) -> int:
	if n <= 2:
		return n
	return fib0(n - 1) + fib0(n - 2)

虽然这种写法是根据数学公式直接转换过来的，十分简单暴力，但是它的运算时间是随n而指数上升的！

55
计算第10个斐波那契数所需时间：0.3194000000000009ms
6765
计算第20个斐波那契数所需时间：1.1687000000000016ms
832040
计算第30个斐波那契数所需时间：108.93619999999999ms
102334155
计算第40个斐波那契数所需时间：12987.193299999999ms

可以看到，从30到40，计算时间直接翻了100倍！更不要说运行fib0(50)了，可能根本等不到运行结果。。。

想办法进行优化

那如果我们有额外需求要求如此之“大”的斐波那契数，要怎么办呢？这里给出两种办法：利用结果缓存、将递归改为迭代。

简直不要太好用的结果缓存

结果缓存是一种缓存技术，即在每次计算任务完成后就把结果保存起来，这样在下次需要时即可直接检索出结果，避免了重复计算。

使用字典进行结果缓存

我们可以将每次计算得到的斐波那契数存入字典中，需要的时候再把它取出来，这样就可以避免重复运算，提高运行效率了。
下面给出了在Python中利用Dict实现结果缓存和在Java中使用Map实现结果缓存的代码：

from typing import Dict

memo: Dict[int, int] = {0: 0, 1: 1}
def fib1(n: int) -> int:
    if n not in memo:
        memo[n] = fib1(n - 1) + fib1(n - 2)
    return memo[n]
	
# output
354224848179261915075
计算第100个斐波那契数所需时间：0.3382000000000003ms

import java.util.*;

public class CalculateFib {
    static Map<Integer, Integer> m = new HashMap<Integer, Integer>();

    public static int fib(int n) {
        if (m.get(n) == null) {
            m.put(n, fib(n - 1) + fib(n - 2));
        }
        return m.get(n);
    }

    public static void main(String[] args) {
        m.put(0, 0);
        m.put(1, 1);
        System.out.println(CalculateFib.fib(20));
    }
}

// output
102334155
Spend time:134100.0ns

比较一下现在的效率和之前的效率，怎么样，是不是有了飞一般的提升？不过，使用字典并不是Python最方便的结果缓存方法，因为在Python里有一个内置的装饰器，可以自动为任何函数缓存结果。

自动化的结果缓存

@functools.lru_cache(maxsize=128, typed=False)是一个为函数提供缓存功能的装饰器，缓存 maxsize 组传入参数，在下次以相同参数调用时直接返回上一次的结果。
如果 maxsize 设为 None，LRU 特性将被禁用且缓存可无限增长。
如果 typed 被设置为 true ，不同类型的函数参数将被分别缓存。 如果 typed 为 false ，实现通常会将它们视为等价的调用，只缓存一个结果。(有些类型，如 str 和 int ，即使 typed 为 false ，也可能被分开缓存）。
我们只需要在最开始实现的fib0()函数上加上装饰器即可，非常简单友好，不是吗？

from functools import lru_cache
@lru_cache(maxsize=None)
def fib0(n: int) -> int:
	if n <= 2:
		return n
	return fib0(n - 1) + fib0(n - 2)

但是其实，就算利用结果缓存，因为还是利用递归的原因，回溯存在上限，还是无法计算一些大数，比如fib(1000)。

Traceback (most recent call last):
RecursionError: maximum recursion depth exceeded

这种情况下，我们就改用迭代法来求斐波那契数了。

迭代法

递归解决方案是反向求解，而迭代则是正向求解，也就是说，我们不再是从n往前求解，而是从0开始推导出n。

def fib2(n: int) -> int:
    if n == 0:
        return n
    last: int = 0
    next: int = 1
    for _ in range(1, n):
        last, next = next, last + next
    return next
	
# output
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
计算第500个斐波那契数所需时间：0.30870000000000203ms

因为利用了迭代法的原因，我们可以在此基础上将这个函数写成生成器，这样就可以输出到n的每一个斐波那契数了。

from typing import Generator

def fib3(n: int) -> Generator[int, None, None]:
    yield 0
    if n > 0: yield 1
    last: int = 0
    next: int = 1
    for _ in range(1, n):
        last, next = next, last + next
        return next
		
if __name__ == "__main__":
	for i in fib3(50):
		print(i)

---

希望本文章能够帮到您~