迭代与递归 — 有哪些权衡？

迭代 使用循环；递归 使用自调用。它们在功能上是等价的（用一种做的任何事都可以用另一种做），但在清晰度和成本上有所不同。

并排比较

# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total


 ():
     n == :
         
     n + sum_rec(n - )

比较

何时使用哪种

• 对简单的线性遍历和栈深度可能很大时，使用 迭代。
• 当问题本质上是递归的（树、图、回溯）且深度有界时，使用 递归。

陷阱

深度递归存在栈溢出风险；当深度无界时，将热递归代码转换为迭代（通常使用显式栈）。

为什么这很重要

选择正确的风格可以保持代码既正确又易读。

递归使树和图的代码优雅，但了解其内存成本可以让你避免在深度输入上崩溃。

当面试官要求你"将其转换为迭代"时，这种权衡判断正是他们探究的内容。