递归是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。在计算机编程里,递归指的是一个过程:函数不断引用自身,直到引用的对象已知。使用递归解决问题,思路清晰,代码少。但是在 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 代入上面的函数,手动执行一下这个函数。
看完上面的文字表述,估计早就云里雾里了,文字表述就是下图所示的递归树。
从这棵树中我们可以看到有着大量的重复计算,这样会耗费大量的时间与空间,我们需要把计算的中间结果保存在一个地方,这就是下面要讲的非递归实现。在实现之前我要先说一个事!
注意:有人可能会想因为 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 装饰器效率高。
本文分享自 Python机器学习算法说书人 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!