一、课上练习

编程练习

1. 阿克曼函数：L3081

二、知识总结

✨ 递推（迭代）

递推是一种利用循环结构来重复计算的方法。在递推中，问题的每个后继状态都是从前一个状态直接推导出来的，整个过程中不涉及多个分支的自我调用。递推的核心在于找到一个递推公式，通过公式从已知状态逐步推导出目标状态。

✨ 递归

递归是一种函数自我调用的过程，用来解决分而治之的问题。递归函数通过调用自身的同名函数来达到重复计算的目的，并且每次调用时问题规模都有所减小，直至达到边界条件（基案）。递归的关键在于将原问题拆分为更小的同类子问题。

✨ 实现方式对比

递推的实现方式：

• 使用循环结构（如 for 或 while 循环）
• 显式地通过迭代来更新状态
• 通常更直观，因为它直接反映了从初始状态到结果状态的计算过程

递归的实现方式：

• 函数中调用自身
• 需要适当的边界条件来停止递归
• 可以更简洁地表达，特别是在解决复杂问题时，代码更为简练

✨ 性能和资源消耗

递推的性能特点：

• 空间效率高，因为不需要额外的函数调用堆栈
• 在执行速度上通常比递归快，因为没有函数调用和返回的开销

递归的性能特点：

• 空间效率较低，每一次函数调用都会消耗堆栈空间，且在调用深度很大时可能导致堆栈溢出
• 执行速度可能不如递推快，特别是当递归调用非常频繁时

✨ 应用场景

递推适用场景： 适合于那些可以直接从一个状态推到下一个状态的问题，如斐波那契数列的计算、简单的数列求和等。

递归适用场景： 适合于解决复杂的问题，如快速排序、归并排序、搜索算法等，这些问题可以自然地分解成更小的子问题。

✨ 递推与递归的对比

✨ 执行示例对比

递推求斐波那契数列

以求 F(6) 为例，递推公式为 F(n) = F(n-1) + F(n-2)，初始值 F(1)=1, F(2)=1：

从前到后，每步只依赖前两步的结果，空间上只需要保存两个变量。

递归求斐波那契数列

同样求 F(6)，递归的调用树为：

1F(6)
2├── F(5)
3│   ├── F(4)
4│   │   ├── F(3)
5│   │   │   ├── F(2) → 1
6│   │   │   └── F(1) → 1
7│   │   └── F(2) → 1
8│   └── F(3)
9│       ├── F(2) → 1
10│       └── F(1) → 1
11└── F(4)
12    ├── F(3)
13    │   ├── F(2) → 1
14    │   └── F(1) → 1
15    └── F(2) → 1

注意 F(4) 被计算了 2 次，F(3) 被计算了 3 次，F(2) 被计算了 5 次。这就是递归的重复计算问题，总调用次数随 n 呈指数增长。

递推 vs 递归的性能对比（以斐波那契为例）

可以看出，对于相同的问题，朴素递归的效率远低于递推。但递归可以通过记忆化技术优化到与递推相同的效率。

✨ 解题步骤详解

遇到一个需要"从已知推未知"的问题时：

1. 找出递推关系：分析第 n 步的结果如何从第 n-1 步（或更早的步骤）推导出来。这是最关键的一步。
2. 确定初始值（边界条件）：递推需要起点，递归需要基案。例如斐波那契数列的 F(1)=1, F(2)=1。
3. 选择实现方式：
   • 如果关系简单且方向明确，用递推（循环）实现，效率更高。
   • 如果问题天然具有"拆分子问题"的结构（如树的遍历、排列组合），用递归更自然。
4. 考虑优化：递归有重复计算时，用记忆化数组存储已计算的结果，避免重复计算。

✨ 常见错误

• 递归忘记写基案：没有终止条件的递归会无限调用下去，导致栈溢出（Stack Overflow）错误。
• 递推初始值设错：初始值错误会导致整个数列都是错的。例如把 F(0)=0 当成 F(0)=1，所有后续值都会偏差。
• 递归层数太深：C++ 默认栈空间有限（通常 1~8MB），如果递归深度超过几万层就会栈溢出。遇到这种情况应改用递推。
• 递推方向搞反：递推必须从已知推向未知，即先计算小的再计算大的。如果方向反了，依赖的值还未计算，结果就是错的。
• 混淆递推下标：使用数组存递推结果时，下标从 0 还是从 1 开始要统一，否则容易导致越界或答案偏移。

三、课后练习

编程练习

1. 汉诺塔的移动次数：L3082