……续上回斐波那契数列与Python的尾递归蹦床 连载【2】
6. 非尾递归的实用化方案
如之前所说,斐波那契数列的典型递归解法时间复杂度为O(1.618 ^ n),耗时指数式快速上升,没有实用价值
仔细看递归调用过程会发现,Calculate_Fibonacci_sequence(n-1) + Calculate_Fibonacci_sequence(n-2),这二元递归过程会有很多重复性中间结果
那么在递归过程中把得到中间结果用字典保存起来,每当一次递归调用都查字典看是否为相同参数的调用,如果是就直接返回字典里保存的值
这样算法时间复杂度就降为O(n)。通过一个缓存技巧,让时间复杂度降到可用程度
开始写出这个递归缓存装饰器。Python里装饰器应用非常普遍,在很多情境下方便的模块化级联
from functools import wraps
def recursive_function_cache(func):
'用于缓存递归函数的装饰器代码。使用方法:在定义函数的前一行写装饰器“@recursive_function_cache”'
cache = dict()
@wraps(func)
def wrapper(*args, **kwargs):
parameters = (tuple.__repr__(args), dict.__repr__(kwargs))
if parameters not in cache:
cache.update({parameters : func(*args, **kwargs)})
return cache.__getitem__(parameters) #返回缓存的函数值
return wrapper
让我们来试一下效果,算第100项
>>> print('Fibonacci number= ', Fibonacci_sequence_02(100))
Fibonacci number= 354224848179261915075
原来卡住的情况没有了,秒出结果
好,再试一下算第1200项
>>> print('Fibonacci number= ', Fibonacci_sequence_02(1200))
RecursionError: maximum recursion depth exceeded while calling a Python object
报栈溢出错误
又是一个对于实用化的障碍。Python默认设置的栈空间不大,只有1000。Python官方不建议大家用递归,尽量写成迭代循环的。并且官方理念是默认设不大的栈空间,如果程序有递归过深的问题就能在运行时早暴露,早改写
不过有时递归写法确实简洁清晰,在对效率没有要求时还是可以用的
那么对递归过程出现溢出错误,一个解决方案就是,动态增加设置的限制值
可能会想到还是用装饰器这个很优雅的写法来实施
然而,当考虑还要在递归函数运行结束后恢复recursionlimit原值
装饰器就无法单独简单完成这个目标了(各位可有什么好想法,欢迎在下方留言探讨^_^)
我用函数参数传入方式来实现这个解决方案
import sys
def dynamic_increase_recursion_limit(func_str):
'加载可能溢出的递归函数,动态增加栈空间限制值。使用方法:dynamic_increase_recursion_limit("函数(参数)")'
Increased_limit = 1000
previous_recursion_limit = sys.getrecursionlimit()
while True:
try:
result = eval(func_str)
sys.setrecursionlimit(previous_recursion_limit)
return result
except RecursionError:
sys.setrecursionlimit(sys.getrecursionlimit() + Increased_limit)
来试一下效果
>>> print('Fibonacci number= ', dynamic_regulation_recursion_limit('Fibonacci_sequence_02(1200)'))
Fibonacci
number=
54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800
运行时间测时同前例,Total time: 0.012642秒
问题解决
让没有实用价值的斐波那契数列递归解法变成可用的递归解法
未完待续……
网友评论