Python 哪些可以代替遞歸的演算法？

01-12

所有的遞歸調用，都可以做CPS變換改寫成尾遞歸形式，然後尾遞歸可以改寫成循環：

def fact(n): if n == 0: return 1 else: return n * fact(n - 1)


id = lambda x: x
def factCPS(n):

    def f(n, k):

        if n == 0:

            return k(1)

        else:

            return f(n - 1, lambda x: k(n * x))
    return f(n, id)
def factNoRec(n):

    def factory(n, k):

        return lambda x: k(n * x)
    k = id

    while True:

        if n == 0:

            return k(1)

        else:

            k = factory(n, k)

            n -= 1
def factHolyCrap(n):

    k = ()

    while True:

        if n == 0:

            x = 1

            while k:

                x = k[0] * x

                k = k[1]

            return id(x)

        else:

            k = (n, k)

            n -= 1

if __name__ == "__main__": print([f(5) for f in [fact, factCPS, factNoRec, factHolyCrap]])

以上是階乘的三種寫法，第一種用遞歸，第二種經過CPS變換消除general recursion，第三種將尾遞歸改寫成循環，徹底消除了遞歸。然而，空間消耗仍然是O(n)的，因為這一系列k在內存中組成了一個長度為O(n)的閉包鏈。

我們這裡的Continuation，仍然採用了Python中的高階函數來表示，而使用Continuation的時候，自然就受到了Python函數調用的局限：沒有尾遞歸優化，所以除了Continuation鏈自身佔用的O(n)內存以外，調用Continuation也會使call stack消耗O(n)內存。怎樣拋開這個call stack一定增長的詛咒？除了我們第三步將尾遞歸改為循環以外，還需要額外多做一個變換：defunctionalization，也就是不再用Python自身的高階函數表示Continuation，而是自己實現一個continuation類，將context封裝到這個類裡面，然後最後在循環調用continuation的時候，就不再有任何的函數調用過程，真正擺脫了call stack深度限制。參見第四個版本。這裡的context很簡單，就只有一個自由變數n，我直接用tuple鏈表示這個continuation了。

最後，第三個版本，用C++寫就不需要那個噁心吧唧的factory方法了。Python的scoping規則坑真箇是名不虛傳：

int fact(int n) { std::function& k = [](int x) { return x; }; for (; if (n == 0) return k(1); else { k = [=](int x) { return k(x * n); }; --n; } }

遞歸過程中需要維護一個調用棧

如果不想遞歸，硬是要循環，那麼可以自己手動來維護這個調用棧

這樣唯一的好處或許就是解除了最大遞歸深度的限制吧。。。

不是完全沒有解決方案：

Does Python optimize tail recursion?

尾遞歸 @Canto Ostinato 巨巨提到了，Python 沒有尾遞歸優化也指出了，這個問題可以簡單地用 trampoline 解決：

def trampoline(func, *args, **kwargs): def trampolined_func(*args, **kwargs): result = func(*args, **kwargs) while: result = result() return result return trampolined_func

拿之前答案里提到的 cps 變換後的 fact 函數演示下用法：

from functools import partial


id = lambda x: x
def fact_cps(n):

    def func(n, k):

        if n == 0:

            return partial(k, 1)

        else:

            return partial(func, n - 1, lambda x: partial(k, n * x))

    return trampoline(func)(n, id)

fact_cps(1025)

原理很簡單，用 partial 函數把遞歸改成惰性調用，然後循環調用之。

（吐槽一下 python 的 functools 真的很難用啊。。以至於大部分人都記不起來 python 標準庫里還有這個

給邵大神補一個java sample

public class RecursionEliminationSample { int factorRec(int n) { if (n == 0) return 1; else return n * factorRec(n-1); }


    int factor(int n) {

        Function& k = (x) -&> x;

        while(true) {

            if (n == 0)

                return k.apply(1);

            else {

                final Function& k0 = k;

                final int n0 = n;

k = (x) -&> k0.apply(n0 * x); n -= 1; } } } }

https://github.com/kachayev/fn.py#trampolines-decorator

https://github.com/lihaoyi/macropy#tail-call-optimization

時代積累的遞歸轉迭代的技術。

然後用自己的棧模擬即可。

用循環實現？

，話j

可以自己建個棧來保存狀態。你只需要搞明白在遞歸的時候程序往棧上面放了些什麼，然後用自己的棧模擬即可。

技巧上倒是可以參照從fortran時代積累的遞歸轉迭代的技術。