……续上回 Fibonacci数列高效解法大全及时间复杂度分析 连载【1】
4. 生成器式尾递归解法
前面尾递归是用的return，在Python里还可以替换为yield，这样尾递归函数就变成了尾递归生成器
变成yield尾递归有个好处，可以不用考虑栈空间限制了，不断地next()直到获得最终结果没问题
def Fibonacci_sequence_04 (n: int) -> int: #参数n是表示求第n项Fibonacci数
assert isinstance(n, int), 'n is an error of non-integer type.'
import types
def Calculate_Fibonacci_sequence (n: int, prev_num: int =0, current_num: int =1) -> int:
'返回单项的yield式尾递归解法'
if n>=2:
yield Calculate_Fibonacci_sequence(n-1, current_num, prev_num+current_num)
elif n==1:
yield current_num
if n>=1:
var_cfs = Calculate_Fibonacci_sequence (n)
while isinstance(var_cfs, types.GeneratorType):
var_cfs = next(var_cfs)
return var_cfs
elif n==0:
return 0
else:
return None
测时同前例，Total time: 0.006211秒
5. yield from生成器式尾递归解法
yield作尾递归的生成器有个问题，就是不能直接用于for循环
解决办法就是yield改成yield from。这样就可以用for循环来获取生成器的终值了。例如：
for result in Fibonacci_sequence(n):
print(result)
但是，yield尾递归的无栈限制的好处就没有了，当递归很深时，又重新出现了栈溢出
这是因为yield from对尾递归调用做了递归式yield生成器管道，就又冒出栈深度限制
破解之道就是还搬出“蹦床”技巧
尾递归生成器使用时为获取终值还要套一层for，既然因为破解栈深限制加个装饰器，那我正好把获取终值功能也加进去。这样使用尾递归生成器就跟函数一样了，如：
Fibonacci_sequence(n)
下面来看完整的展开尾递归装饰器及yield from尾递归解法斐波那契数
import functools
import inspect
import types
class TailCallException(Exception):
def __init__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
def Tail_recursion_generator_expansion(generator):
'用于尾递归生成器展开的装饰器代码。使用方法：在定义生成器的前一行写装饰器“@Tail_recursion_generator_expansion”'
@functools.wraps(generator)
def wrapper(*args, **kwargs):
frame = inspect.currentframe()
if frame.f_back and frame.f_back.f_back and frame.f_code == frame.f_back.f_back.f_code: #先判断当前是否为递归调用（递归的话是_wrapper->被装饰函数->_wrapper），再判断是否存在前级和前前级调用
raise TailCallException(*args, **kwargs)
else:
while True:
try:
g = generator(*args, **kwargs)
while isinstance(g, types.GeneratorType):
g=next(g)
return g
except TailCallException as e:
args = e.args
kwargs = e.kwargs
return wrapper
def Fibonacci_sequence_05 (n: int) -> int: #参数n是表示求第n项Fibonacci数
assert isinstance(n, int), 'n is an error of non-integer type.'
@Tail_recursion_generator_expansion
def Calculate_Fibonacci_sequence (n: int, prev_num: int =0, current_num: int =1) -> int:
'返回单项的yield from式尾递归解法'
if n>=2:
yield from Calculate_Fibonacci_sequence(n-1, current_num, prev_num+current_num)
elif n==1:
yield current_num
if n>=1:
return Calculate_Fibonacci_sequence (n)
elif n==0:
return 0
else:
return None
测时同前例，Total time: 0.013653秒
未完待续……
