……續(xù)上回? Fibonacci數(shù)列高效解法大全及時(shí)間復(fù)雜度分析 連載【1】
4.? 生成器式尾遞歸解法
前面尾遞歸是用的return，在Python里還可以替換為yield厢蒜，這樣尾遞歸函數(shù)就變成了尾遞歸生成器
變成yield尾遞歸有個(gè)好處丸冕，可以不用考慮椇垦校空間限制了筒繁，不斷地next()直到獲得最終結(jié)果沒問題
def Fibonacci_sequence_04 (n: int) -> int:? #參數(shù)n是表示求第n項(xiàng)Fibonacci數(shù)
??? 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:
? ? ? ? '返回單項(xiàng)的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
測(cè)時(shí)同前例，Total time: 0.006211秒
5.? yield from生成器式尾遞歸解法
yield作尾遞歸的生成器有個(gè)問題阳欲，就是不能直接用于for循環(huán)
解決辦法就是yield改成yield from舵盈。這樣就可以用for循環(huán)來獲取生成器的終值了。例如：
for?result in Fibonacci_sequence(n):
??? print(result)
但是球化，yield尾遞歸的無棧限制的好處就沒有了秽晚，當(dāng)遞歸很深時(shí)，又重新出現(xiàn)了棧溢出
這是因?yàn)閥ield from對(duì)尾遞歸調(diào)用做了遞歸式y(tǒng)ield生成器管道筒愚，就又冒出棧深度限制
破解之道就是還搬出“蹦床”技巧
尾遞歸生成器使用時(shí)為獲取終值還要套一層for赴蝇，既然因?yàn)槠平鈼Ｉ钕拗萍觽€(gè)裝飾器，那我正好把獲取終值功能也加進(jìn)去巢掺。這樣使用尾遞歸生成器就跟函數(shù)一樣了句伶，如：
Fibonacci_sequence(n)
下面來看完整的展開尾遞歸裝飾器及yield from尾遞歸解法斐波那契數(shù)
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:? #先判斷當(dāng)前是否為遞歸調(diào)用（遞歸的話是_wrapper->被裝飾函數(shù)->_wrapper）陆淀，再判斷是否存在前級(jí)和前前級(jí)調(diào)用
? ? ? ? ? ? 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: #參數(shù)n是表示求第n項(xiàng)Fibonacci數(shù)
??? 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:
? ? ? ? '返回單項(xiàng)的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
測(cè)時(shí)同前例考余，Total time: 0.013653秒
未完待續(xù)……
