尾遞歸簡(jiǎn)介
尾遞歸是函數(shù)返回最后一個(gè)操作是遞歸調(diào)用，則該函數(shù)是尾遞歸。
遞歸是線性的比如factorial函數(shù)每一次調(diào)用都會(huì)創(chuàng)建一個(gè)新的棧(last-in-first-out)通過(guò)不斷的壓棧，來(lái)創(chuàng)建遞歸, 很容易導(dǎo)致棧的溢出。而尾遞歸則使用當(dāng)前棧通過(guò)數(shù)據(jù)覆蓋來(lái)優(yōu)化遞歸函數(shù)。
階乘函數(shù)factorial, 通過(guò)把計(jì)算值傳遞的方法完成了尾遞歸。但是python不支出編譯器優(yōu)化尾遞歸所以當(dāng)遞歸多次的話還是會(huì)報(bào)錯(cuò)(學(xué)習(xí)用)。
eg：
|
1
2
3
4
5
6
7
|
def factorial(n, x): if n == 0: return x else: return factorial(n-1, n*x)print factorial(5, 1) # 120 |
尾遞歸優(yōu)化
這里用到了斐波那契數(shù)來(lái)作為例子.線性遞歸的算法由于太過(guò)一低效就被我們Pass掉了，我們先來(lái)看尾遞過(guò)方式的調(diào)用：
|
1
2
3
4
5
6
7
8
|
(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) |
這段程序我們來(lái)測(cè)試一下，調(diào)用 Fib(1001)結(jié)果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
>>> 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)... >>> Fib(1001)70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L>>> |
如果我們用Fib(1002)，結(jié)果，茶幾了，如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
..... File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in FibRuntimeError: maximum recursion depth exceeded>>> |
好了，現(xiàn)在我們來(lái)尾遞歸優(yōu)化
我們給剛才的Fib函數(shù)增加一個(gè)Decorator,如下：
|
1
2
3
4
5
6
7
8
9
|
@tail_call_optimizeddef 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) |
恩，就是這個(gè)@tail_call_optimized的裝飾器 ，這個(gè)裝飾器使Python神奇的打破了調(diào)用棧的限制。
這下即使我們Fib(20000)，也能在780ms跑出結(jié)果（780ms是以前博文提到那臺(tái)2000元的上網(wǎng)本跑出來(lái)的結(jié)果）
不賣(mài)關(guān)子了，下面我們來(lái)看看這段神奇的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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() 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 |
使用的方法前面已經(jīng)展示了，令我感到大開(kāi)眼界的是，作者用了拋出異常然后自己捕獲的方式來(lái)打破調(diào)用棧的增長(zhǎng)，簡(jiǎn)直是太匪夷所思了。而且效率問(wèn)題，和直接尾遞歸Fib相比大概造成了五倍的時(shí)間開(kāi)銷(xiāo)。
最后很不可思議的，尾遞歸優(yōu)化的目的達(dá)成了。
