优化函数递归

递归是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。使用递归解决问题，思路清晰，代码少。但是在 Python 中，使用递归会消耗很大的空间，可能还会产生大量的重复的计算。所以我们应该想办法消除递归，下面我以斐波那契序列为例讲解几种消除递归的方法。

斐波那契数列

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

递归实现

看完上面的描述，用递归实现斐波那契数列非常简单，代码如下：

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

既然递归这么简单为什么还要消除递归呢？下面我们以 n = 5 代入上面的函数，手动执行一下这个函数。

1. 我要计算 fib(5)，那么我就需要计算 fib(4)和 fib(3)。
2. 我要计算 fib(4)，那么我就需要计算 fib(3)和 fib(2)；我要计算 fib(3)，那么我就需要计算 fib(2)和 fib(1)。
3. 我要计算 fib(3)，那么我就需要计算 fib(2)和 fib(1)；我要计算 fib(2)，那么我就需要计算 fib(1)和 fib(0)；我要计算 fib(2)，那么我就需要计算 fib(1)和 fib(0)。

看完上面的文字表述，估计早就云里雾里了，文字表述就是下图所示的递归树。

从这棵树中我们可以看到有着大量的重复计算，这样会耗费大量的时间与空间，我们需要把计算的中间结果保存在一个地方，这就是下面要讲的非递归实现。在实现之前我要先说一个事！

注意：有人可能会想因为 Python 递归有次数限制，最多 1000 次，所以需要消除递归。如果是因为这个消除递归那就真的是闲着无聊没事干！因为这个次数限制是可以修改的，直接使用 sys 模块中的 setrecursionlimit 函数来设置，这个函数接受一个参数，这个参数是新设置最大次数。如果说你无法提前预估最大次数，那么就要消除递归！

非递归实现——栈

因为递归带来的效率问题太严重了，我们需要想方设法消除递归。在消除递归之前，我们要先想一下递归怎么执行的？递归就是函数不断的调用自身，在内存中产生许多调用堆栈，这不就是传说中的数据结构——栈吗？在 Python 中，我们只要初始化一个空列表就是初始化一个空栈，列表对象的 append 方法就相当于入栈，列表对象的 pop 方法就相当于出栈。知道这些用栈消除递归的代码也就可以写出来了，代码如下：

def fib_with_stack(n):
    stack = []
    a = [0, 1, 0]
    result = 0
    for i in range(n//3):
        a[2] = a[0]+a[1]
        stack.append(a[0])
        a[0] = a[1]+a[2]
        stack.append(a[1])
        a[1] = a[2]+a[0]
        stack.append(a[2])
    a[2] = a[0]+a[1]
    stack.append(a[0])
    if n % 3 == 0:
        result = stack.pop()
    a[0] = a[1]+a[2]
    stack.append(a[1])
    if n % 3 == 1:
        result = stack.pop()
    a[1] = a[2]+a[0]
    stack.append(a[2])
    if n % 3 == 2:
        result = stack.pop()
    return result

代码的逻辑看上去非常复杂，但是这么做确实避免了重复计算，不相信可以测试一下，测试代码如下：

if __name__ == '__main__':
    from time import perf_counter_ns
    start = perf_counter_ns()
    fib(10)
    print(perf_counter_ns()-start)

    start = perf_counter_ns()
    fib_with_stack(10)
    print(perf_counter_ns()-start)

运行结果如下：

从运行结果中可以看出很明显用栈实现非递归的效率高。用栈实现非递归虽然效率高，但是代码逻辑太复杂了，不到万不得已真的不想用。如果我可以提前预知递归最大次数，又想避免重复计算，又不想用栈实现非递归那该怎么办？有两种办法：用循环实现和直接使用 functools 模块中的 lru_cache 装饰器。其中用循环实现这种方法并不通用，因为有些递归函数不能写成循环，比如阿克曼函数。下面我们直接来看使用 lru_cache 的效率。

functools.lru_cache

这个装饰器的使用非常简单，直接给出代码：

from functools import lru_cache


@lru_cache(maxsize=1000)
def fib_with_stack(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_with_stack(n-1)+fib_with_stack(n-2)

下面我们再来测试一下，测试代码不变，依旧是上面的测试代码，这次直接给出运行结果：

从运行结果可以看出用 lru_cache 装饰器效率高。