我如何优化这个递归函数来计算其数字等于和的 n 位十六进制数的数量？

Question

def hexify(summ, l, count = 0):
    if sum == 0:
        return 1
    for i in range(16):
        if i < summ and l > 1:
            count += hexify(summ-i, l-1)
        elif i == summ and l > 0:
            count += 1
    return count 
            
hexa = str(input())[2:] #input tag eg. 0x0121
summ = sum(int(digit, 16) for digit in hexa)
print(hexify(summ, len(hexa)) - 1)

这段代码的作用是找到位数等于某个和的n位十六进制数的个数。例如，如果给定的十六进制数是 0x12，则该函数将 return 3（意味着有 3 个十六进制数的数字总和为三，不包括 0x12，即 0x03 0x30 和 0x21）。

问题是给定的约束条件是 1 > 1 > 10，一旦长度 l 超过 6，代码就会停止运行。我该如何优化它？（需要递归）

Answer 1

如果你想加速你的代码，你可以使用缓存装饰器

@functools.cache(user_function) Simple lightweight unbounded function cache. Sometimes called “memoize”.

Returns the same as lru_cache(maxsize=None), creating a thin wrapper around a dictionary lookup for the function arguments. Because it never needs to evict old values, this is smaller and faster than lru_cache() with a size limit.

https://docs.python.org/dev/library/functools.html#functools.cached_property

from functools import cache

@cache
def hexify(summ, l, count = 0):
    if sum == 0:
        return 1
    for i in range(16):
        if i < summ and l > 1:
            count += hexify(summ-i, l-1)
        elif i == summ and l > 0:
            count += 1
    return count 
            
hexa = str(input())[2:] #input tag eg. 0x0121
summ = sum(int(digit, 16) for digit in hexa)
print(hexify(summ, len(hexa)) - 1)

我如何优化这个递归函数来计算其数字等于和的 n 位十六进制数的数量？

How do I optimize this recursive function that counts the number of n-digit hexadecimal numbers whose digits equal a sum?

python

algorithm

recursion