按下回车键跳到正文

Python递归优化

在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):  
    if n == 0:
        yield total
    else:
        yield ret(n-1, total+n)

 

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

From LzSkyline's Blog : https://www.lzskyline.com/archives/495

当前没有任何回复哦,快成为第一个吃螃蟹的人~

发表评论

电子邮件地址不会被公开。 必填项已用*标注