How to optimize this recursion function?-CodePudding

This is really similar to Fibonacci Sequence problem. I understand the DP optimization with Fibonacci function using the for loop, but I'm having hard time to connect to this problem.

The recursion function I want to optimize is:

def cal(n): if n <= 0: return 1 else: return cal(n-25) cal(n-26)

CodePudding user response：

Something like this may help:

(It's inspired by previous post)


from functools import cache

@cache
def cal(n):
    if n <= 0:
        return 1
    else:
        return cal(n-25)   cal(n-26)



print(cal(100))

CodePudding user response：

The idea of a "for loop optimization" is that we calculate cal(0), cal(1), cal(2), ... consecutively. And when we want cal(n), we already have cal(n-25) and cal(n-26) stored in an array.

So, the following solution has linear complexity for non-negative n:

def cal(n):
    mem = [1]  # cal(0) is 1
    for i in range(1, n   1):
        num = 1 if i - 25 < 0 else mem[i - 25]
        num  = 1 if i - 26 < 0 else mem[i - 26]
        mem.append (num)
    return mem[-1]

One can further optimize to make all the values cal(1), cal(2), ..., cal(n) globally available after calculating the last of them.