递归与迭代的权衡
将递归版阶乘和斐波那契转换为迭代循环，并解释 Python 的递归限制和栈大小何时使迭代更合适。
递归与迭代的权衡 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
递归与迭代的二重性
每个可以递归编写的算法也可以迭代编写，反之亦然。递归版本通常更贴近问题的数学定义，而迭代版本让您可以明确控制内存，并避免栈溢出风险。选择哪一种是基于可读性、深度限制和性能要求的务实决定。
在面试中，能够给出两个版本并解释它们之间的权衡，是掌握程度很高的体现。
阶乘：递归与迭代
阶乘是最典型的例子。递归版本直接编码了数学定义 n! = n × (n-1)!。由于存在 n 个待处理的返回值，它使用 O(n) 的栈空间。迭代版本从 1 循环到 n，只使用 O(1) 的空间。当 n = 1000 时，递归版本会触及 Python 的默认限制；迭代版本则可以处理任意大的 n。
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)斐波那契：指数级与线性
朴素递归的斐波那契实现的时间（time）复杂度为 O(2^n)，对于较大的 n 来说慢得无法接受。迭代实现的时间（time）复杂度为 O(n)，空间复杂度为 O(1)。记忆化递归（下一课）同样具有 O(n) 的时间复杂度，但由于记忆字典和 O(n) 的栈，需要 O(n) 的空间。对于斐波那契问题，迭代方法在所有指标上都是最优的。当 n = 50 时，朴素递归需要几秒，而迭代实现只需几微秒。
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large n树遍历：递归与迭代
递归树遍历自然且简洁，因为树的结构与递归相互对应。但对于严重偏斜的树（本质上是一个链表），递归深度等于树高 = O(n)，存在栈溢出的风险。使用显式栈的迭代版本没有深度限制，并且允许栈大小在堆上增长，而不是占用调用栈。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]归并排序：递归与迭代（自底向上）
归并排序天然适合递归（拆分、递归、合并）。迭代式自底向上归并排序完全避免递归：从大小为 1 的子数组开始，将相邻的子数组对合并为大小为 2 的子数组，然后是大小为 4 的子数组，以此类推；每次遍历都将子数组大小翻倍。自底向上归并排序的 time 复杂度为 O(n log n)，空间复杂度为 O(n)（用于合并缓冲区），栈空间复杂度为 O(1)。
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]递归明显更优的情况
当问题具有可以直接映射到调用图的树状结构、基本情况自然明确，并且深度有界时（平衡树以及分治问题的深度为 O(log n)），递归就能发挥优势。示例包括 JSON 解析、目录遍历、博弈树和回溯问题。在这些情况下，与等价的迭代版本相比，递归代码更短、更清晰，也更容易证明其正确性。
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]迭代明显更优的情况
出现以下情况时，应选择迭代：深度为 O(n) 且 n 很大（在安全的 Python 代码中，超过约 500）；递归版本和迭代版本同样易读（例如斐波那契数列、阶乘）；或者问题本质上是顺序处理的，不存在自然的子问题分解。使用简单循环从左到右处理数组——例如计算运行和、滑动窗口、双指针——时，应始终采用迭代。
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choice将 DFS 递归转换为迭代
一种系统化的方法是：将递归参数压入显式栈，就可以把每个递归 DFS 转换为迭代。关键在于，递归调用 f(args) 等价于压入 args 并进入循环。对于后序处理（需要先得到子节点的结果，再处理父节点），可能需要采用两遍处理方法或使用访问标记。
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]递归的性能开销
Python 中的每次递归调用都有不可忽略的开销：系统会创建一个新帧（在堆上分配内存）、初始化局部变量，并存储返回地址指针。基准测试表明，Python 中的函数调用开销大约为每次 100–200 纳秒。对于深度为 10^6 的递归，这会累积出 0.1–0.2 秒的纯开销，与算法本身的工作量无关。迭代循环则完全避免了这种开销。
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')面试中的选择
在编程面试中，如果有多种选择，可以询问自己：“递归深度是否由 O(log n) 限制？”如果是，递归就没有问题。“递归深度是否为 O(n)？”——应优先选择迭代，或者说明在生产环境中会将其转换为迭代。“问题是否天然呈树状结构或属于分治问题？”——倾向于使用递归。“问题是否是顺序扫描？”——使用迭代。
始终说明您的推理：“这里我会使用递归，因为平衡 BST 的深度为 O(log n)，因此 O(log n) 的栈空间是可以接受的。”
总结：权衡表
总结这些权衡：递归代码通常更短，并且能反映问题结构，但需要 O(深度) 的栈空间，还会产生函数调用开销。迭代代码更长，但只使用 O(1) 的栈空间，并且不会受到递归限制的影响。记忆化递归（下一课）是一种折中方案：保留递归的清晰性，同时消除重复计算。分析解决方案时，请始终明确说明空间复杂度，并将调用栈空间计算在内。
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')快速检查
请检验您对本课中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学到了：当深度为 O(log n) 或问题天然呈树状结构时，优先使用递归；当深度为 O(n) 或问题是顺序处理时，优先使用迭代；朴素递归斐波那契数列的复杂度为 O(2^n)，而迭代版本的 time 复杂度为 O(n)、空间复杂度为 O(1)；以及任何递归 DFS 都可以通过在堆上管理显式栈转换为迭代。接下来，我们将应用记忆化来消除多余的递归调用。
常见问题解答
「递归与迭代的权衡」课时是免费的吗？
是的 — 「递归与迭代的权衡」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「递归与迭代的权衡」这节课中我会学到什么？
将递归版阶乘和斐波那契转换为迭代循环，并解释 Python 的递归限制和栈大小何时使迭代更合适。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「递归与迭代的权衡」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 递归框架：基准情形、信任、构建
- 可视化调用栈
- 递归与迭代的权衡
- 记忆化：缓存递归结果