Python 哪些可以代替递归的算法？

程序员文章站 2022-05-12 20:53:37

...

回复内容：

所有的递归调用，都可以做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]])

递归过程中需要维护一个调用栈

如果不想递归，硬是要循环，那么可以自己手动来维护这个调用栈

这样唯一的好处或许就是解除了最大递归深度的限制吧。。。给邵大神补一个java sample

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

    int factor(int n) {
        FunctionInteger, Integer> k = (x) -> x;
        while(true) {
            if (n == 0)
                return k.apply(1);
            else {
                final FunctionInteger, Integer> k0 = k;
                final int n0 = n;

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

用循环实现？可以自己建个栈来保存状态。你只需要搞明白在递归的时候程序往栈上面放了些什么，然后用自己的栈模拟即可。
技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。不是完全没有解决方案：
Does Python optimize tail recursion? 时代积累的递归转迭代的技术。然后用自己的栈模拟即可。，话j