一般遞歸與尾遞歸

一般遞歸

def normal_recursion(n):
    if n == 1:
        return 1
    else:
        return n + normal_recursion(n-1)

執行：

normal_recursion(5)
5 + normal_recursion(4)
5 + 4 + normal_recursion(3)
5 + 4 + 3 + normal_recursion(2)
5 + 4 + 3 + 2 + normal_recursion(1)
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
15

可以看到, 一般遞歸, 每一級遞歸都需要調用函數, 會創建新的棧,

隨著遞歸深度的增加, 創建的棧越來越多, 造成爆棧:boom:

尾遞歸

尾遞歸基于函數的尾調用, 每一級調用直接返回函數的返回值更新調用棧,而不用創建新的調用棧, 類似迭代的實現, 時間和空間上均優化了一般遞歸!

def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n-1, total+n)

執行：

tail_recursion(5)
tail_recursion(4, 5)
tail_recursion(3, 9)
tail_recursion(2, 12)
tail_recursion(1, 14)
tail_recursion(0, 15)
15

可以看到, 每一級遞歸的函數調用變成"線性"的形式.

深入理解尾遞歸

呃, 所以呢? 是不是感覺還不夠過癮... 誰說尾遞歸調用就不用創建新的棧呢?

還是讓我們去底層一探究竟吧

int tail_recursion(int n, int total) {
    if (n == 0) {
        return total;
    }
    else {
        return tail_recursion(n-1, total+n);
    }
}

int main(void) {
    int total = 0, n = 4;
    tail_recursion(n, total);
    return 0;
}</code></pre> 
  
反匯編
 
  
 
   
 
$ gcc -S tail_recursion.c -o normal_recursion.S
 
 
   
 
$ gcc -S -O2 tail_recursion.c -o tail_recursion.S gcc開啟尾遞歸優化
 
 
  
 
  
對比反匯編代碼如下(AT&T語法)
 
  
 
  
可以看到, 開啟尾遞歸優化前, 使用call調用函數, 創建了新的調用棧(LBB0_3);
 
  
而開啟尾遞歸優化后, 就沒有新的調用棧生成了, 而是直接pop
 
  
bp指向的 _tail_recursion 函數的地址(pushq %rbp)然后返回,
 
  
 
  
仍舊用的是同一個調用棧!
 
  
存在的問題
 
  
雖然尾遞歸優化很好, 但python 不支持尾遞歸，遞歸深度超過1000時會報錯
 
  
RuntimeError: maximum recursion depth exceeded
 
  
一個牛人想出的解決辦法
 
  
實現一個 tail_call_optimized 裝飾器
 
  
#!/usr/bin/env python2.4

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:
    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()
    # 為什么是grandparent, 函數默認的第一層遞歸是父調用,
    # 對于尾遞歸, 不希望產生新的函數調用(即:祖父調用),
    # 所以這里拋出異常, 拿到參數, 退出被修飾函數的遞歸調用棧!(后面有動圖分析)
    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, 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(10000)</code></pre> 
  
為了更清晰的展示開啟尾遞歸優化前、后調用棧的變化和tail_call_optimized裝飾器拋異常退出遞歸調用棧的作用, 我這里利用 pudb調試工具 做了動圖 <br/>
 
  
開啟尾遞歸優化前的調用棧
 
  
 
  
開啟尾遞歸優化后(tail_call_optimized裝飾器)的調用棧
 
  
 
  
通過pudb右邊欄的stack, 可以很清晰的看到調用棧的變化.
 
  
因為尾遞歸沒有調用棧的嵌套, 所以Python也不會報 RuntimeError: maximum recursion depth exceeded 錯誤了!
 
  
這里解釋一下 sys._getframe() 函數:
 
  
sys._getframe([depth]):
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, ValueEfror is raised. The default for depth is zero,
returning the frame at the top of the call stack.

即返回depth深度調用的棧幀對象.
import sys
def get_cur_info():
    print sys._getframe().f_code.co_filename  # 當前文件名
    print sys._getframe().f_code.co_name  # 當前函數名
    print sys._getframe().f_lineno # 當前行號
    print sys._getframe().f_back # 調用者的幀</code></pre> 
  
 
 
  
 
 
  
來自：https://segmentfault.com/a/1190000007641519