实际示例
树遍历：二叉搜索树
递归方法
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def recursive_inorder(root):
result = []
def traverse(node):
if node:
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
迭代转换
def iterative_inorder(root):
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
递归转换流程图
graph TD
A[递归方法] --> B{识别递归模式}
B --> C[创建显式栈]
C --> D[模拟递归调用]
D --> E[手动管理状态]
深度优先搜索：图遍历
递归深度优先搜索
def recursive_dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
recursive_dfs(graph, neighbor, visited)
return visited
迭代深度优先搜索
def iterative_dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(neighbor for neighbor in graph[vertex]
if neighbor not in visited)
return visited
转换策略比较
| 策略 |
内存 |
性能 |
复杂度 |
| 递归 |
高 |
低 |
代码更简单 |
| 迭代 |
低 |
高 |
更复杂 |
高级示例：归并排序
递归实现
def recursive_merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = recursive_merge_sort(arr[:mid])
right = recursive_merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
迭代归并排序
def iterative_merge_sort(arr):
width = 1
n = len(arr)
while width < n:
for i in range(0, n, 2*width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
arr[i:i+2*width] = merge(left, right)
width *= 2
return arr
性能考量
在 LabEx，我们建议：
- 为了清晰和易读性使用递归
- 对于性能关键部分转换为迭代
- 分析和基准测试你的具体用例
