D12. 递归、分治与二分查找
2.1 分治思想的核心：相同子问题与边界条件
目标：理解分治法的适用条件及递归终止的必要性。
2.1.1 分治三要素
分治法通过将问题分解为若干个相同或相似的子问题，递归求解后合并结果。其核心条件：
- 子问题独立性：子问题之间无重叠（如斐波那契数列的递归版本因重复计算导致低效）。
- 边界条件：当子问题规模足够小时，可直接求解（如排序问题的终止条件是
n=1）。- 解的可合并性：子问题的解能合并为原问题的解（如归并排序的合并操作）。
示例：汉诺塔问题
python
def hanoi(n, source, helper, target):
if n == 1: # 边界条件
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n-1, source, target, helper) # 分解为子问题
print(f"Move disk {n} from {source} to {target}")
hanoi(n-1, helper, source, target) # 合并解2.2 递归实现阶乘：分治思想的入门案例
目标：通过阶乘案例掌握递归的三要素。
2.2.1 阶乘递归公式
python
def factorial(n):
if n == 0: # 终止条件
return 1
return n * factorial(n-1) # 递归调用关键点：
- 递归三要素：
- 终止条件（
n=0或n=1）。 - 问题分解：
n! = n × (n-1)!。 - 递归调用：每次缩小问题规模（
n→n-1）。
- 终止条件（
- 时间复杂度：O(n)，因递归深度为n。
2.3 循环替代递归：阶乘的非递归实现
目标：理解递归与循环的等价性及效率差异。
2.3.1 循环实现阶乘
python
def factorial_iter(n):
result = 1
for i in range(1, n+1):
result *= i # 累乘代替递归调用
return result对比分析：
| 特性 | 递归实现 | 循环实现 |
|---|---|---|
| 代码复杂度 | 简洁易读 | 需手动维护状态 |
| 空间复杂度 | O(n)（栈深度） | O(1) |
| 效率 | 可能栈溢出（n大时） | 更高效 |
2.4 有序性与算法效率：二分查找的动机
目标：理解有序数组如何通过冗余信息降低复杂度。
2.4.1 有序数组的优势
在有序数组中，可利用元素的相对位置快速定位目标值，而非逐个遍历。例如：
- 线性搜索：时间复杂度O(n)（如无序数组）。
- 二分查找：时间复杂度O(logn)（有序且无重复元素）。
问题：如何利用有序性将问题规模减半？
分治策略：
- 取中间元素与目标比较。
- 若匹配，返回位置；否则，缩小搜索范围至左半或右半区间。
2.5 递归实现二分查找
目标：掌握分治法在递归中的具体应用。
2.5.1 递归代码实现
python
def binary_search(arr, target, low, high):
if low > high: # 终止条件：未找到
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid # 找到目标
elif arr[mid] < target:
return binary_search(arr, target, mid+1, high) # 右半区间递归
else:
return binary_search(arr, target, low, mid-1) # 左半区间递归关键点：
- 参数传递：通过
low和high控制子问题范围。 - 时间复杂度：O(logn)，因每次将问题规模减半。
- 空间复杂度：O(logn)（递归栈深度）。
2.6 循环实现二分查找
目标：通过循环实现分治思想，提升效率。
2.6.1 循环代码实现
python
def binary_search_iter(arr, target):
low, high = 0, len(arr)-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1对比分析：
- 循环优势：
- 空间效率：O(1)（无递归栈开销）。
- 避免栈溢出：适合大规模数据（如数组长度10⁶）。
- 逻辑等价性：两种实现均遵循分治策略的核心步骤。
2.7 递归与栈的等价性
目标：理解递归本质是栈的隐式实现。
2.7.1 用栈模拟递归阶乘
python
def factorial_stack(n):
stack = []
result = 1
while n > 0 or stack:
if n > 0:
stack.append(n) # 保存当前n值
n -= 1
else:
n = stack.pop() # 恢复上一层n值
result *= n
n = 0 # 避免重复入栈
return result关键点：
- 栈模拟：手动维护递归调用的参数和返回状态。
- 适用场景：当递归深度过大时，可手动优化为栈结构。
知识回顾
- 分治法：通过分解问题为相同子问题，递归求解并合并结果。
- 递归三要素：终止条件、问题分解、递归调用。
- 二分查找：利用有序性将问题规模减半，时间复杂度O(logn)。
- 递归与循环：递归简洁但可能低效，循环需手动维护状态，但空间更优。
- 栈的作用：递归本质上依赖栈结构，可显式模拟以优化性能。
课后练习
选择题：以下哪种情况最适合使用分治法？
- A. 计算斐波那契数列第n项（递归版）
- B. 在有序数组中查找元素
- C. 统计字符串中字符出现次数
代码题：将汉诺塔递归代码改为循环实现（提示：使用栈保存移动步骤）。
分析题：假设数组长度为n，写出递归二分查找的时间复杂度递推式，并解出其解。
扩展阅读
- 递归优化：
- 记忆化搜索：通过缓存子问题结果（如斐波那契数列的动态规划）。
- 尾递归优化：将递归调用置于函数末尾，部分语言可优化为循环。
- 分治应用：
- 快速排序（分解为分割点左、右子数组）。
- 大整数乘法（将乘法分解为子问题相加）。
- 调试技巧：通过打印递归深度或中间结果，定位栈溢出或逻辑错误。