跳到主要内容

递归 (Recursion)

递归（Recursion）概述​

概念​

  • 递归是一种算法，也是一种编程技巧，应用非常广泛。
  • 递归求解问题的分解过程：去的过程叫“递”，回来的过程叫“归”
  • 应用：DFS深度优先搜索、前中后序二叉树遍历

优缺点：​

  • 优点：
    • 递归代码表达能力强，写起来简洁
  • 缺点：
    • 空间复杂度高
    • 有堆栈溢出的风险
    • 存在重复计算
    • 过多的函数调用会耗时较多

递归公式Demo​

f(n)=f(n-1)+1 其中，f(1)=1

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

什么场景的问题适合用递归解决​

需要满足以下三个条件

  • 一个问题的解可以分解为几个子问题的解
  • 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  • 存在递归终止条件
    • 不能出现无限循环

如何编写递归代码​

  • 核心思想：写出递推公式，找到终止条件，然后将递推公式转化为代码
  • 方法：
    • 找到如何将大问题分解为小问题的规律，并且写出递推公式
    • 推敲终止条件
    • 将递归公式和终止条件翻译成代码
  • 注意：
    • 只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要视图用人脑去分解递归的每个步骤（重复的步骤交给计算机完成）

递归常见问题​

  • 递归代码要警惕堆栈溢出
    • 可以声明一个全局变量来控制递归深度，可以一定程度避免堆栈溢出
  • 递归代码要警惕重复计算
    • 通过某种数据结构来保存已经求解过的值，从而避免重复计算
  • 过多的函数调用会耗时较多，空间复杂度高

递归代码改非递归代码​

  • 递归代码都可以改为迭代循环的非递归写法
  • 本质上是：将自动递归改为手动递归，本质问题没有解决
  • 实现：
    1. 抽象递推公式
    2. 初始值和边界条件
    3. 用迭代循环实现
0%