基于Numba的递归函数性能优化：缩小与迭代实现的差距

• 改成尾递归形式：如果所用语言支持尾递归优化（比如PyPy、Scala等），把递归逻辑调整为尾递归——也就是递归调用是函数的最后一步操作，没有后续计算。这样编译器可以把递归转化为迭代，彻底消除栈帧创建的开销。如果是Python这种默认不支持尾递归的语言，可以用装饰器手动模拟，或者直接用PyPy运行来获得优化。

• 复用中间状态，减少内存开销：别每次递归都新建列表或对象存储中间组合，改用同一个可变对象（比如列表），递归前添加元素，递归结束后弹出。这样能避免频繁的内存分配和拷贝，大幅提升速度。举个Python的例子：

  def optimized_recursive_cartesian(lists, idx=0, current=None):
      if current is None:
          current = []
      if idx == len(lists):
          yield tuple(current)
          return
      for item in lists[idx]:
          current.append(item)
          yield from optimized_recursive_cartesian(lists, idx+1, current)
          current.pop()
  

• 手动用栈模拟递归：如果不想依赖语言的尾递归优化，直接用栈数据结构手动模拟递归过程。把递归需要的状态（当前处理的层级、当前组合）存在栈里，用循环遍历栈元素，完全消除递归的栈帧开销，性能和原生迭代几乎一致，同时还保留了泛化能力。示例代码：

  def stack_based_cartesian(lists):
      stack = [(0, [])]
      while stack:
          idx, current = stack.pop()
          if idx == len(lists):
              yield tuple(current)
              continue
          # 反转元素入栈，保证输出顺序和递归一致
          for item in reversed(lists[idx]):
              new_current = current.copy()
              new_current.append(item)
              stack.append((idx + 1, new_current))
  

• 局部化递归函数：把递归函数定义在主函数内部，让它直接访问外部函数的局部变量，减少参数传递的开销，同时解释器能对局部变量做更多优化，提升执行速度。

• 缓存重复子问题（按需使用）：如果你的递归逻辑里存在重复的子问题（比如不同路径会处理相同的输入），用缓存装饰器（比如Python的functools.lru_cache）缓存子问题的结果，避免重复计算。但像笛卡尔积这种无重复子问题的场景，这个方法就没必要用了。

• 对齐迭代版本的细节：检查递归版本的内部操作，和迭代版本保持一致——比如迭代里直接操作列表，递归里就别额外加类型转换、冗余赋值这类步骤，减少不必要的性能损耗。

• 换用JIT编译器的解释器：比如Python中，CPython的递归性能瓶颈主要来自解释器的栈帧开销，换成PyPy运行的话，JIT编译器会自动优化递归调用，甚至把它转化为迭代，性能能追上甚至超过迭代版本。

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