Python递归优化

博客文章迁移: 2018-05-15 11:17

为了少写几行代码直接用递归做的, 测试的时候才想起来递归太多次了, 没法正确执行..

然后就去搜了一下递归优化方面的文章, 发现可以改成尾递归来让python优化执行.

一般递归:

def recsum(x):
 if x == 1:
 return x
 else:
 return x + recsum(x - 1)

尾递归:

def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n-1, total+n)

我看了一下我当时提交的代码, return时并没有用到表达式, 已经属于尾递归的形式了, 所以说递归应该是没法用了.

接着我又看到了一个曲线救国的方法, 改用生成器:

把需要优化的函数的return改成yield，外面套个装饰器，就叫tail_call_opm。装饰器最内层的逻辑是
while True:
    try:
        ret=next(ret)
    except:
        return ret

作者：NightyNight链接：https://www.zhihu.com/question/29717057/answer/178798202来源：知乎着作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处

这样就改成了:

def ret(n, total=0):

(PS:但是这样代码就太长了= =所以我改成迭代交了上去,逃…

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。