Python递归很慢

Question

我是 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) 时没有遇到任何问题。

这种递归尝试可以挽救吗？

Answer 1

您正在计算 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(3^m)，即使 m=15 也会导致大约 15 百万 次递归调用，而不是实际需要的 15 个。