盒子
文章目录
  1. 简介
    1. 递归:Recusion
    2. 函数结构
    3. 计算机的实现方法
  2. 递归一般有三种形式:
    1. 缓存(Memoization)
    2. 分治(Divide and Conquer)
      1. 分治模板
    3. 回溯(Backtracking)
    4. 分治(Divide and Conquer)
    5. 回溯(Backtracking)
      1. 回溯模板

递归总结

简介

递归:Recusion

Recusion is an approach to solve problems using a function that calls itself as a subroutine

函数结构

一般来讲,递归函数 = 终止条件(Base case) + 递归关系(Recusion relation)。

Base case:最小问题的解决方式
Recusion relation:大问题和小问题的关系

计算机的实现方法

  1. 任何一个函数的调用,计算机会在内存中生成一块区域,用于存放函数的参数,返回的地址等,这块区域叫做「栈」。
  2. 递归函数的调用会生成一系列的栈

递归一般有三种形式:

缓存(Memoization)

以经典的 斐波那契数列 为例

  1. Base case:

$F(0) = 0;F(1) = 1$

  1. Relation

$F(n) = F(n - 1) + F(n - 2)$

根据这两个条件很容易得出递归函数,而为什么需要引入缓存:

如上图:f(4) = f(3) + f(2)

而 f(3) = f(2) + f(1)

在计算 $f(3)$ 时,我们其实已经计算过 $f(2)$ 的结果,将 $f(2)$ 存入缓存则可以减少以空间换时间。

相关题目:

爬楼梯

分治(Divide and Conquer)

分而治之,几乎等同与标准的递归,唯一的区别是。最后需要将子问题的结果合并。

  • Divide:将问题 $S$ 分解为子问题 {$S1$, $S2$, …$Sn$}
  • Conquer:递归解决小问题
  • Combine:合并每个结果

98. 验证二叉搜索树 为例

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
var isValidBST = function(root) {
if (!root) {
return true
}
function valid(root, low = -Infinity, high = Infinity) {
if (!root) {
return true
}
if (root.left && (root.left.val >= root.val) || root.val >= high ) {
return false
}
if (root.right && (root.right.val <= root.val) || root.val <= low ) {
return false
} // base case

return (valid(root.left, low, root.val) && valid(root.right, root.val, high))
}

return valid(root)
};
  • base case: 如果左边的节点大于当前节点或者当前节点大于父节点,则为 fasle。右子树同理条件反之。
  • 分治:将树 分解为左子树和右子树的校验的子问题
  • 结合:将结果合并

将问题分解为:验证左子树 和 验证右子树。

分治模板

function divideAndConquer() {
[S1, S2, ...Sn] = divide(S)
rets = for (var i = 0; i < Things.length; i++) {
divideAndConquer(Things[i])
}
[R1, R2, ...Rn] = rets
return Combine([R1, R2, ...Rn])
}

回溯(Backtracking)

回溯问题的一般形式:寻找所有满足 XXX 条件的结果,并且问题可以递归实现。

LC22: 括号生成 为例

=======
Base case

$F(0) = 0;F(1) = 1$

Relation

$F(n) = F(n - 1) + F(n - 2)$

根据这两个条件很容易得出递归函数

```js

为什么需要引入缓存:

st=>start: F(4)
op1=>operation: F(3)
op2=>operation: F(2)
op3=>operation: F(1)

st->op1->op2

分治(Divide and Conquer)

回溯(Backtracking)

1.

LC22: 括号生成

/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
const result = []
function backtracking(charactor = '', left = 0, right = 0) {
if (charactor.length === 2 * n) {
result.push(charactor)
}
if (left < n) {
backtracking(charactor + '(', left + 1, right)
}
if (left > right) {
backtracking(charactor + ')', left, right + 1)
}
}
backtracking('', 0, 0)
return result
};
  • 使用两个 if 判断是否可以添加左右括号。不满足 if 的则为无效表达式
  • 使用 charactor 表示当前变量。

回溯模板

function backtrack(candiate) {
if findSolution(candiate) {
outPut(candiate)
return
}
for (nextCandidate in listOfCandiate) {
if (is_validate(nextCandidate)) {
place(nextCandidate)
backtrack(nextCandidate)
remove(nextCandidate)
}
}
}

相关习题: