python遞歸_Python當中的尾遞歸優化

本文讨論Python中尾遞歸優化以及尾遞歸優化原理。

本文共讨論兩點内容，一個是

如何進行尾遞歸優化

，一個是

遞歸優化原理

。

1. 如何進行尾遞歸優化

Python當中實際上沒有尾遞歸優化的功能，遞歸受到棧長度限制，例如我們用遞歸實作斐波那契數列計算的時候，

def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)
           

當我們執行

fib(1000)
           

則程式會報錯，因為超過了最大棧長度限制。

Traceback (most recent call last):
  File "C:/test_Tail_Recursion.py", line 48, in <module>
    print(fib(2000))
  File "C:/test_Tail_Recursion.py", line 43, in fib
    return fib(i - 1, next, current + next)
  File "C:/test_Tail_Recursion.py", line 43, in fib
    return fib(i - 1, next, current + next)
  File "C:/test_Tail_Recursion.py", line 43, in fib
    return fib(i - 1, next, current + next)
  [Previous line repeated 994 more times]
  File "C:/test_Tail_Recursion.py", line 40, in fib
    if i == 0:
RecursionError: maximum recursion depth exceeded in comparison
           

是以我們需要嘗試一下對尾遞歸進行優化。

對尾遞歸進行優化參考下面的代碼。

Tail Call Optimization Decorator " Python recipes " ActiveState Code​code.activestate.com

但這個代碼實際上是在Python2.4的環境下運作，我們需要優化為支援Python3.6環境的代碼，代碼如下

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 decorated5
    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
           

該函數實際上是一個裝飾器，是以我們在調用的時候，隻需要

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)
           

即可實作函數在超過調用棧深度的情況下完成函數功能。

2. 尾遞歸優化原理介紹

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
           

其中

f = sys._getframe()實際上傳回一個frameobject，簡稱f

f中的 f.f_back實際上會傳回調用棧下一個元素的對象，也就是目前元素的上一個進棧對象

f.f_back.f_back顧名思義就是上上一個

f_code指的是目前代碼路徑

是以，當我們函數fib(1000)在裝飾器下執行的時候

1. fib(1000, 0, 1)在執行前首先進入裝飾器函數，f.f_back為main()函數也就是調用fib的函數
2. fib(1000, 0, 1)下的f.f_back.f_back為None，是以進入else邏輯（調用棧深度為1）
3. 執行fib(1000, 0, 1)
4. fib(1000, 0, 1)調用fib(999, 1, 1)
5. 這時函數fib(999, 1, 1)進入裝飾器函數，符合if條件（調用棧深度為2）， 執行raise TailRecurseException,并将(999, 1, 1)參數傳入TailRecurseException
6. 該參數被fib(1000, 0, 1)的except捕捉， 通過TailRecurseException将參數(999, 1, 1)傳遞給fib() ，進而進行下一次調用
7. 重複過程4 - 6

上述為該裝飾器與函數的工作過程

總結：

我們通過不停重用調用棧棧頂元素，參數通過TailRecurseException進行傳遞，這樣棧深度最大為2，永遠不會超過Python所規定的範圍，進而完成我們功能的實作