Python递归memoization优化：给定递归公式的函数效率提升

假设我们有如下递归公式：

基于该递归公式的原始实现如下：

def f(k):
    if(k <= 2):
        return k
    elif(k % 2 ==0):
        return 5*f(k/2) + 1
    else:
        return f((k-1)/2) + 2  

可通过以下几种方案提升运行效率与稳定性：

1. 修正浮点除法的类型与精度问题 #

原代码使用/执行浮点除法，递归过程中传入的参数会从整数变为浮点数（比如f(4)会传入2.0而非整数2），不仅会导致返回值类型不符合预期，当k数值极大时还会出现浮点数精度丢失的问题。
替换为Python整数除法//即可解决问题，修正后的基础递归版本：

def f(k):
    if k <= 2:
        return k
    elif k % 2 == 0:
        return 5 * f(k // 2) + 1
    else:
        return f((k - 1) // 2) + 2

2. 改用迭代实现，消除递归开销与栈溢出风险 #

原递归实现每一层都需要生成函数调用栈帧，不仅有额外的函数调用性能开销，还会受Python默认递归深度限制（默认约1000层），当k数值较大（比如k为2的2000次方）时会直接触发RecursionError栈溢出。
利用递归的折半特性，可通过迭代记录运算路径的方式实现，时间复杂度同样为O(log k)，但无额外调用开销，也不受递归深度限制：

def f(k):
    if k <= 2:
        return k
    ops = []
    current = k
    # 先记录从顶层k到基例的所有运算规则
    while current > 2:
        if current % 2 == 0:
            ops.append(('mul5_add1',))
            current = current // 2
        else:
            ops.append(('add2',))
            current = (current - 1) // 2
    # 从基例开始反向执行所有运算，得到最终结果
    res = current
    for op in reversed(ops):
        if op[0] == 'mul5_add1':
            res = 5 * res + 1
        else:
            res = res + 2
    return res

3. 频繁调用场景下增加缓存机制 #

如果业务场景需要多次调用f计算不同的k值，不同大k的子问题会大量重叠（比如计算f(1024)时会复用f(512)、f(256)等中间结果）。此时可以使用Python内置的lru_cache装饰器增加缓存，避免重复计算：

from functools import lru_cache

@lru_cache(maxsize=None)
def f(k):
    if k <= 2:
        return k
    elif k % 2 == 0:
        return 5 * f(k // 2) + 1
    else:
        return f((k - 1) // 2) + 2

该方案仅适合递归实现，若使用迭代版本可自行维护一个字典存储已计算过的k值，实现效果一致。

内容的提问来源于stack exchange，提问作者Nicolas H