Python recursion is very slow

Question

I am a novice at python, but was surprised at how slow this recursive call took to execute:

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)    

I ran it on IDLE, python 3.6. I added the INT stuff but it did not help. I had no problems running the standard factorial recursion and printing factorial(106).

Can this attempt at recursion be salvaged?

Answer 1

You are computing daH(m-1) 3 times, making the algorithm slower than necessary. Instead, calculate it just once and bind the result to a local variable. (Also, not necessary to cast to 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

Calling the function three times instead of once may not seem like much, but remember that those calls will stack exponentially! You call it three times, and each of those again call it three times, and so on. This results in a complexity of O(3^m), which even for m=15 results in about 15 million recursive calls, as opposed to the 15 that are actually necessary.