在思否上面看到了這樣一篇的文章:講述了如何去除python對遞歸的限制,看完后不得不對他佩服,不過仔細(xì)想想也是挺合理的!他主要是通過拋出異常來結(jié)束之前的棧然后新開棧來調(diào)用函數(shù),具體代碼如下:
#!/usr/bin/env python3.5
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException(Exception):
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back \
and f.f_back.f_back.f_code == f.f_code:
# 拋出異常
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException as e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
print(factorial(2000))
具體原理:
當(dāng)遞歸函數(shù)被該裝飾器修飾后, 遞歸調(diào)用在裝飾器while循環(huán)內(nèi)部進(jìn)行, 每當(dāng)產(chǎn)生新的遞歸調(diào)用棧幀時(shí): f.f_back.f_back.f_code == f.f_code:, 就捕獲當(dāng)前尾調(diào)用函數(shù)的參數(shù), 并拋出異常, 從而銷毀遞歸棧并使用捕獲的參數(shù)手動(dòng)調(diào)用遞歸函數(shù). 所以遞歸的過程中始終只存在一個(gè)棧幀對象, 達(dá)到優(yōu)化的目的.
不過這種企業(yè)需求真的很少!在python中遞歸深度最大是950+次(具體多少次真的不好說,不同的機(jī)子和平臺不一樣的!而且同一臺機(jī)子的不同執(zhí)行時(shí)間也不一樣!這里就不去探究他!但是一定小于999次)
思否原文連接https://segmentfault.com/a/1190000007641519
關(guān)于尾遞歸: 當(dāng)遞歸調(diào)用是函數(shù)體中最后執(zhí)行的語句并且它的返回值不屬于表達(dá)式一部分時(shí)稚瘾， 這個(gè)遞歸就是尾遞歸道逗。
現(xiàn)代的編譯器就會(huì)發(fā)現(xiàn)這個(gè)特點(diǎn)， 生成優(yōu)化的代碼匕坯， 復(fù)用棧幀蜻底。斐波那契數(shù)列算法中因?yàn)橛袀€(gè)n * factorial(n-1) , 雖然也是遞歸骄崩，但是遞歸的結(jié)果處于一個(gè)表達(dá)式中，還要做計(jì)算， 所以就沒法復(fù)用棧幀了刁赖，只能一層一層的調(diào)用下去搁痛。
雖然尾遞歸調(diào)用也會(huì)創(chuàng)建新的棧, 但是我們可以優(yōu)化使得尾遞歸的每一級調(diào)用共用一個(gè)棧!
關(guān)于尾遞歸優(yōu)化還有另外一種思路,那就是漢諾塔思路:
具體查看網(wǎng)址https://www.cnblogs.com/tgycoder/p/6063722.html
相對于上面的算法,漢諾塔思路會(huì)更加好!但是漢諾塔思路設(shè)計(jì)的東西不會(huì)無限遞歸,雖然他和上面的拋出異常的方式都是尾遞歸的每一級調(diào)用共用一個(gè)棧,但是拋出異常的方式利用了cpython的機(jī)制 "漏洞" 來實(shí)現(xiàn)自己無限遞歸的運(yùn)作方式!但是漢諾塔思路沒利用!
其中一種尾遞歸優(yōu)化的方式其實(shí)就是建立在漢諾塔的思路上面的!比如下面的代碼:
def tail_recursion(n, total=0):
if n == 0:
return total
else:
return tail_recursion(n-1, total+n)##這一步必須沒有表達(dá)式,而是只有call本身函數(shù)
print(tail_recursion(993))##但是還是受到了cpython解釋器的限制!這里把993更改
##為999會(huì)發(fā)現(xiàn)拋出遞歸最大深度的異常
