跳至主要內容

3.2 递归算法

3.2 递归算法

递归是一种应用非常广泛的算法，很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件

写递归代码的关键

  1. 找到将大问题分解为小问题的规律，并且基于此写出递推公式，再推敲终止条件，最后将递推公式和终止条件翻译成代码。
  2. 遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
function f(n) {
	if (n == 1) return 1; // 终止条件
	return f(n - 1) + 1; // 递推公式
}

所有的递归代码都可以改写为迭代循环的非递归写法。

弊端

  1. 警惕栈溢出：可以声明一个全局变量来控制递归的深度，从而避免栈溢出。
  2. 警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。

相关题目

题号标题题解标签难度力扣
344反转字符串[✓]双指针 字符串🟢🀄️open in new window 🔗open in new window
24两两交换链表中的节点[✓]递归 链表🟠🀄️open in new window 🔗open in new window
118杨辉三角[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
119杨辉三角 II[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
206反转链表[✓]递归 链表🟢🀄️open in new window 🔗open in new window
92反转链表 II[✓]链表🟠🀄️open in new window 🔗open in new window
21合并两个有序链表[✓]递归 链表🟢🀄️open in new window 🔗open in new window
509斐波那契数[✓]递归 记忆化搜索 数学 1+🟢🀄️open in new window 🔗open in new window
70爬楼梯[✓]记忆化搜索 数学 动态规划🟢🀄️open in new window 🔗open in new window
104二叉树的最大深度[✓]树 深度优先搜索 广度优先搜索 1+🟢🀄️open in new window 🔗open in new window
124二叉树中的最大路径和[✓]树 深度优先搜索 动态规划 1+🔴🀄️open in new window 🔗open in new window
226翻转二叉树[✓]树 深度优先搜索 广度优先搜索 1+🟢🀄️open in new window 🔗open in new window
50Pow(x, n)[✓]递归 数学🟠🀄️open in new window 🔗open in new window
779第K个语法符号位运算 递归 数学🟠🀄️open in new window 🔗open in new window
95不同的二叉搜索树 II[✓]树 二叉搜索树 动态规划 2+🟠🀄️open in new window 🔗open in new window
剑指 Offer 62圆圈中最后剩下的数字[✓]递归 数学🟢🀄️open in new window
Copyright © 2024 2xiao