跳到主要内容

递归算法

递归的求解过程分几步？​

  • 递归: 把规模大的问题分解为形式相同、规模更小的子问题;
  • 递推过程: 原问题不断分解, 直到触达最小子问题;
  • 回归过程: 从最小子问题的解逐层合并, 还原出原问题的解;
  • 前提: 子问题与原问题同构, 且规模严格变小;

写递归要先确定哪两件事？​

  • 递归公式: 用子问题的解表示原问题的解;
  • 终止条件: 规模小到可以直接求解的边界;
def recursion(大规模问题):
    if 递归终止条件:
        return 递归终止时的处理方法
    return recursion(小规模问题)
  • 顺序: 先写终止条件再写递归调用, 漏掉终止条件会无限递归;

递归为什么会有栈溢出？​

  • 实现: 递归依赖函数调用栈, 一次递归占用一个栈帧;
  • 风险: 递归深度超过调用栈容量时抛出栈溢出;
  • 规避: 减小递归深度、把递归改写成迭代, 或用显式栈模拟调用栈;

递归为什么会重复计算？​

  • 成因: 同一个子问题被不同分支多次求解, 例如朴素斐波那契;
  • 代价: 时间随递归深度指数增长;
  • 规避: 用数组或哈希表缓存已求出的子问题解, 即记忆化;

递归和迭代怎样互相转换？​

  • 等价性: 任何递归都可用显式栈改写成迭代, 任何迭代也可改写成尾递归;
  • 转换代价: 迭代省下栈帧开销, 但状态维护代码通常更长;
  • 选择: 深度可控且逻辑天然分治时用递归, 深度不可控或追求常数优化时用迭代;