概念
遞歸是函數(shù)不停的調用自身直到滿足結束條件退出蟆融。遞歸存在一個很大的問題就是隨著遞歸的深入笼裳，占用大量的椙﹂荩空間憎夷，最后很有可能導致棧溢出。
尾遞歸是遞歸的一種特例昧旨。尾遞歸從名字上理解就是把遞歸放到函數(shù)的最后拾给。在尾遞歸中祥得，先執(zhí)行計算的部分，然后把計算結果鸣戴，作為參數(shù)傳入下一次遞歸啃沪。
實例
眾所周知斐波那契數(shù)列是遞歸的一個例子。
遞歸實現(xiàn)
def fibonacci(n):
if n <= 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
當我們調用fibonacci(1001)的時候窄锅，會拋出下面的異常：
RecursionError: maximum recursion depth exceeded in comparison
從異炒辞В看已經超出了遞歸調用的最大深度，系統(tǒng)的最大深度可以通過sys.getrecursionlimit()獲得入偷，這個設置的默認值是1000追驴。當然我們可以修改這個值達到我們的要求。
尾遞歸實現(xiàn)
def fibonacci(n, b1=1, b2=1, c=3):
if n < 3:
return 1
else:
if n == c:
return b1 + b2
else:
return fibonacci(n, b1=b2, b2=b1+b2, c=c+1)
尾遞歸的特點就是最后返回的結果就是下次調用返回的結果疏之。
同樣我們也調用fibonacci(1001)殿雪，很遺憾還是拋出了異常：
RecursionError: maximum recursion depth exceeded in comparison
這說明了python沒有對尾遞歸做任何的優(yōu)化。對于尾遞歸來說每次調用的函數(shù)除了參數(shù)的數(shù)值不一樣锋爪，其他完全一樣丙曙，也就是說完全可以僅僅修改一下參數(shù)的數(shù)值利用棧內保存的函數(shù)就能處理。
神奇的裝飾器
既然沒有優(yōu)化其骄，那就沒有其他辦法了嗎亏镰？當然是有的，這里不得不提一下一個神奇的裝飾器@tail_call_optimized拯爽。(參照：http://code.activestate.com/recipes/474088/)
import sys
class TailRecurseException(BaseException):
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
這個裝飾器實現(xiàn)的原理確實精妙索抓，當進行第二次調用的時候就拋出一個異常，把參數(shù)修改一下毯炮，然后返回調用逼肯。這樣就保證了不會有大量的函數(shù)堆積在棧里面。
然后把剛才的尾遞歸修改一下：
@tail_call_optimized
def fib(n, b1=1, b2=1, c=3):
if n < 3:
return 1
else:
if n == c:
return b1 + b2
else:
return fib(n, b1=b2, b2=b1+b2, c=c+1)
然后再調用一下fibonacci(1001)桃煎，沒有異常了篮幢。
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
其他相關
其實對于一些語言是存在尾遞歸優(yōu)化的，比如C語言編譯的時候加優(yōu)化參數(shù) -O2就可以實現(xiàn)备禀。
