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次,使算法慢于必要.相反,只计算一次并将结果绑定到局部变量.(另外,没有必要施放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导致大约1500 万次递归调用,而不是实际需要的15次.