Python中递归函数是否总是低效？两类求解实现耗时差异原因咨询

为什么第二段代码耗时更低 #

• 首版递归代码属于无记忆化的暴力递归，核心缺陷是存在大量重复计算：计算n_family(k,n)时需要同时调用n_family(k-1,n)和n_family(k,n-1)，同一个子问题会被反复触发成千上万次，时间复杂度为指数级的O(2^(k+n))，当k、n超过12时总调用次数会直接爆炸。同时Python每次函数调用都需要完成压栈、传参、出栈的操作，额外开销也会进一步拉长运行时间。
• 第二版是自底向上的动态规划实现，每个子问题（即每个apt[i][j]的数值）只会被计算一次，时间复杂度为线性的O(k*n)，本题限定n最大为14，就算k取值较大，总计算量也非常小。而且全程是直接操作列表做数值赋值，没有额外的函数调用开销，运行速度自然快很多。

Python递归是否总是效率偏低 #

这不是本次的特殊情况，但也并非所有递归的效率都低，可以分场景判断：

1. Python本身默认没有尾递归优化，递归深度超过默认阈值（通常为1000）会直接触发栈溢出，这是Python递归的固有缺陷。
2. 无记忆化、存在大量重复子问题的递归（比如本次的首版实现、普通的斐波那契递归），效率会远低于同逻辑的迭代实现，除了重复计算的开销，多次函数调用的额外开销也会被放大。
3. 如果给递归加上记忆化缓存（比如用functools.lru_cache装饰器），解决重复计算的问题，效率会和迭代实现接近，仅多了少量函数调用的开销，在递归深度不大的场景完全可以正常使用。例如以下加了缓存的递归，运行效率和第二版动态规划代码基本一致：

from functools import lru_cache

@lru_cache(maxsize=None)
def n_family(k, n):
    if k == 0:
        return n
    elif n == 1:
        return 1
    else:
        return n_family(k-1,n) + n_family(k,n-1)

像树的遍历、小规模分治算法这类场景，递归写起来更简洁，深度不大的情况下效率也完全够用。

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