原文出處： neo1218
一般遞歸與尾遞歸
一般遞歸
def normal_recursion(n):
if n == 1:
return 1
else:
return n + normal_recursion(n-1)
執(zhí)行：
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
可以看到, 一般遞歸, 每一級(jí)遞歸都需要調(diào)用函數(shù), 會(huì)創(chuàng)建新的棧,
隨著遞歸深度的增加, 創(chuàng)建的棧越來(lái)越多, 造成爆棧??
尾遞歸
尾遞歸基于函數(shù)的尾調(diào)用, 每一級(jí)調(diào)用直接返回函數(shù)的返回值更新調(diào)用棧,而不用創(chuàng)建新的調(diào)用棧, 類似迭代的實(shí)現(xiàn), 時(shí)間和空間上均優(yōu)化了一般遞歸!
def tail_recursion(n, total=0):
if n == 0:
return total
else:
return tail_recursion(n-1, total+n)
執(zhí)行：
tail_recursion(5)
tail_recursion(4, 5)
tail_recursion(3, 9)
tail_recursion(2, 12)
tail_recursion(1, 14)
tail_recursion(0, 15)
15
可以看到, 每一級(jí)遞歸的函數(shù)調(diào)用變成”線性”的形式.
深入理解尾遞歸
呃, 所以呢? 是不是感覺還不夠過癮… 誰(shuí)說尾遞歸調(diào)用就不用創(chuàng)建新的棧呢?
還是讓我們?nèi)サ讓右惶骄烤拱?/p>
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;
}
反匯編
- $ gcc -S tail_recursion.c -o normal_recursion.S
- $ gcc -S -O2 tail_recursion.c -o tail_recursion.S gcc開啟尾遞歸優(yōu)化
對(duì)比反匯編代碼如下(AT&T語(yǔ)法)
可以看到, 開啟尾遞歸優(yōu)化前, 使用call調(diào)用函數(shù), 創(chuàng)建了新的調(diào)用棧(LBB0_3);
而開啟尾遞歸優(yōu)化后, 就沒有新的調(diào)用棧生成了, 而是直接pop
bp指向的_tail_recursion函數(shù)的地址(pushq %rbp)然后返回,
仍舊用的是同一個(gè)調(diào)用棧!
存在的問題
雖然尾遞歸優(yōu)化很好, 但python 不支持尾遞歸，遞歸深度超過1000時(shí)會(huì)報(bào)錯(cuò)
RuntimeError: maximum recursion depth exceeded
一個(gè)牛人想出的解決辦法
實(shí)現(xiàn)一個(gè) 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, 函數(shù)默認(rèn)的第一層遞歸是父調(diào)用,
# 對(duì)于尾遞歸, 不希望產(chǎn)生新的函數(shù)調(diào)用(即:祖父調(diào)用),
# 所以這里拋出異常, 拿到參數(shù), 退出被修飾函數(shù)的遞歸調(diào)用棧!(后面有動(dòng)圖分析)
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:
# 捕獲異常, 拿到參數(shù), 退出被修飾函數(shù)的遞歸調(diào)用棧
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)
為了更清晰的展示開啟尾遞歸優(yōu)化前、后調(diào)用棧的變化和tail_call_optimized裝飾器拋異常退出遞歸調(diào)用棧的作用, 我這里利用pudb調(diào)試工具做了動(dòng)圖
開啟尾遞歸優(yōu)化前的調(diào)用棧
開啟尾遞歸優(yōu)化后(tail_call_optimized裝飾器)的調(diào)用棧
通過pudb右邊欄的stack, 可以很清晰的看到調(diào)用棧的變化.
因?yàn)槲策f歸沒有調(diào)用棧的嵌套, 所以Python也不會(huì)報(bào)RuntimeError: maximum recursion depth exceeded錯(cuò)誤了!
這里解釋一下 sys._getframe() 函數(shù):
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深度調(diào)用的棧幀對(duì)象.
import sys
def get_cur_info():
print sys._getframe().f_code.co_filename # 當(dāng)前文件名
print sys._getframe().f_code.co_name # 當(dāng)前函數(shù)名
print sys._getframe().f_lineno # 當(dāng)前行號(hào)
print sys._getframe().f_back # 調(diào)用者的幀
更多關(guān)于sys._getframe請(qǐng)看Frame Hacks
