微信号:omret-django

介绍:每日推送django、python相关技术文档,技术趣文等.

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

2016-02-04 08:44 邵成

所有的递归调用,都可以做CPS变换改写成尾递归形式,然后尾递归可以改写成循环:

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)id = lambda x: xdef 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 -= 1def 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 -= 1if __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<int(int)> k = [](int x) { return x; };
    for (; ;)
        if (n == 0)
            return k(1);
        else {
            k = [=](int x) { return k(x * n); };
            --n;
        }
}


著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。
作者:邵成
链接:https://www.zhihu.com/question/36857981/answer/69520229
来源:知乎

 
Django 更多文章 Django框架简介 django-MySQL数据库 如何实现 C/C++ 与 Python 的通信? Django教程1-MVC 程序员的创业陷阱:接私活
猜您喜欢 UI,要做就做最优秀的! iWeb峰会上海站——让移动营销盛典见证H5的繁荣 腾讯高级工程师:一道面试题引发的高并发性能调试思考 流量加密奈我何? 推荐!国外程序员整理的机器学习资源大全