Python递归优化

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

---

在codewars上做题时遇到的坑(https://www.codewars.com/kata/build-a-pile-of-cubes/solutions/python).

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

然后就去搜了一下递归优化方面的文章, 发现可以改成尾递归来让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:但是这样代码就太长了= =所以我改成迭代交了上去,逃…