欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 2022-05-24 14:25:44
...

回复内容:

所有的递归调用,都可以做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? 时代积累的递归转迭代的技术。 然后用自己的栈模拟即可。 ,话jPython 哪些可以代替递归的算法?

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频


网友评论

文明上网理性发言,请遵守 新闻评论服务协议

我要评论
  • Python 哪些可以代替递归的算法?
  • 专题推荐