Python 的遞歸是有最大限制的错沽，超過(guò)這個(gè)限制便會(huì)拋出
RuntimeError: maximum recursion depth exceeded
sys.getrecursionlimit()可以查看遞歸的最大層數(shù)，默認(rèn)為 1000
sys.setrecursionlimit() 可以改變這個(gè)最大層數(shù)
cPython 不支持尾遞歸優(yōu)化眶拉，但有些 hack 的做法可以繞過(guò)千埃，比如 trampoline 這種神奇的技術(shù)。當(dāng)調(diào)用遞歸函數(shù)時(shí)忆植，先插入一個(gè) trampoline 函數(shù)放可。通過(guò)這個(gè)函數(shù)來(lái)調(diào)用真正的遞歸函數(shù)，并且對(duì)其進(jìn)行修改朝刊，不讓它再次進(jìn)行遞歸的函數(shù)調(diào)用耀里，而是直接返回下次遞歸調(diào)用的參數(shù)，由 trampoline 來(lái)進(jìn)行下一次“遞歸“調(diào)用拾氓。這樣一層一層的遞歸調(diào)用就會(huì)變成一次一次的迭代調(diào)用冯挎。
個(gè)人認(rèn)為 如果要使用這種 hack 的做法，不如去使用一種可以對(duì)尾遞歸進(jìn)行優(yōu)化的語(yǔ)言
參考自http://code.activestate.com/recipes/474088/咙鞍，有少許改動(dòng)
#!/usr/bin/env python2.7
# 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
from functools import wraps
class TailRecurseException(BaseException):
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(func):
"""
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.
"""
@wraps(func)
def wrapper(*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 True:
try:
return func(*args, **kwargs)
except TailRecurseException as e:
args = e.args
kwargs = e.kwargs
return wrapper
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n - 1, n * acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
@tail_call_optimized
def fib(i, current=0, next=1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.
這段代碼最精彩地方的就是一發(fā)生遞歸就會(huì)拋出一個(gè)攜帶函數(shù)參數(shù)的自定義異常房官，然后通過(guò)循環(huán)的方式來(lái)再次調(diào)用(傳入捕獲到的參數(shù))。這樣我們雖然寫(xiě)代碼時(shí)寫(xiě)的是遞歸续滋，但是實(shí)際上發(fā)生的迭代翰守。
上面的代碼使用了 sys._getframe() 獲取棧幀，以判斷是否發(fā)生遞歸疲酌。這個(gè)平時(shí)寫(xiě)代碼時(shí)一般很少接觸到蜡峰。
Python 文檔中是這樣表述的
Return a frame object from the call stack. If optional integer depth is given, return the frame object that many calls below the top of the stack. If that is deeper than the call stack, ValueError is raised. The default for depth is zero, returning the frame at the top of the call stack.
CPython implementation detail: This function should be used for internal and specialized purposes only. It is not guaranteed to exist in all implementations of Python.
# 獲取當(dāng)前棧幀對(duì)象
f = sys._getframe()
# 獲取前一個(gè)棧幀對(duì)象
f.f_back
# 獲取棧幀的代碼對(duì)象
f.f_code
# 獲取棧幀的代碼對(duì)象名稱
f.f_code.co_name
另外當(dāng)沒(méi)有前一個(gè)棧幀時(shí)，f.f_back 會(huì)返回 None
回到之前的代碼中徐勃，大致分析一下流程
執(zhí)行 factorial(1000) 事示，由于我們使用了tail_call_optimized 裝飾器，實(shí)際上我們調(diào)用了 wrapper
這時(shí)前一個(gè)棧幀的代碼對(duì)象名稱為 <module> (這里表達(dá)的有點(diǎn)不恰當(dāng)僻肖，大概是這個(gè)意思)肖爵，前前棧幀的代碼對(duì)象名稱為 execfile
進(jìn)入 while True 死循環(huán)，執(zhí)行 func(*args, **kwargs) 創(chuàng)建了新的棧幀臀脏。這時(shí)發(fā)生遞歸調(diào)用又進(jìn)入新的 wrapper 棧幀中劝堪，但是棧幀對(duì)應(yīng)的代碼對(duì)象(f_code)不變冀自，所以這里我們拋出了自定義異常 TailRecurseException ，并將此次遞歸的參數(shù)寫(xiě)入
捕獲到這個(gè)異常后秒啦，并用從異常對(duì)象中讀出的參數(shù)再次執(zhí)行 func(*args, **kwargs)
注意熬粗，我們并沒(méi)有阻止棧幀的線性增長(zhǎng)。
另外還有一種利用 yield 的實(shí)現(xiàn)
