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 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 次，使算法比所需的更慢。相反，只需计算一次并将结果绑定(bind)到局部变量。 (另外，没有必要强制转换为 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 次。