Python递归非常慢

概述我是 python的新手,但对这个递归调用执行速度有多慢感到惊讶： def daH(m:int): if m == 1: return int(1) else: if m <= .5 * (daH(m-1) * (daH(m-1) +1)): return int(daH(m-1)) else: 我是 python的新手,但对这个递归调用执行速度有多慢感到惊讶：

def daH(m:int):    if m == 1:        return int(1)    else:        if m <= .5 * (daH(m-1) * (daH(m-1) +1)):            return int(daH(m-1))        else:            return int(daH(m-1) + 1)print(daH(10)) # prints 4print(daH(11)) # prints 5print(daH(15)) # prints 5    print(daH(16)) # prints 6print(daH(106)) # prints ??? (gave up waiting)

我在IDLE,python 3.6上运行它.我添加了INT的东西,但它没有帮助.运行标准阶乘递归和打印阶乘(106)没有问题.

这种递归尝试能否得到挽救？

解决方法 您计算daH(m-1)3次,使算法慢于必要.相反,只计算一次并将结果绑定到局部变量. (另外,没有必要转换为int)

def daH(m:int):    if m == 1:        return 1    else:        r = daH(m-1)        if m <= .5 * r * (r + 1):            return r        else:            return r + 1

调用该函数三次而不是一次可能看起来不多,但请记住,这些调用将呈指数级堆叠！你把它叫了三次,每个人再称它三次,依此类推.这导致O(3m)的复杂性,即使对于m = 15,也导致大约1500万个递归调用,而不是实际需要的15个.

总结

以上是内存溢出为你收集整理的Python递归非常慢全部内容，希望文章能够帮你解决Python递归非常慢所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。