Python递归非常慢

发布时间：2020-12-20 12:41:28 所属栏目：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: return int(daH(m-1) + 1)print(daH(10)) # prints 4print(daH(11)) #

我是 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 4
print(daH(11)) # prints 5
print(daH(15)) # prints 5    
print(daH(16)) # prints 6

print(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个.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!