递归的三种形式
Published by powerfulyang on Jul 3, 2022
Memorization
将计算结果保存,避免重复计算。
Divide and Conquer
分治,将大问题分解成小问题,各个击破,然后将小问题组合起来。
- Divide
- Conquer
- Combine
Backtracking
回溯法用来解决 N 个 for 循环的问题
不断试错,知错就改。类似于暴力搜索, 但是会剪枝优化。
一般要求返回所有满足条件的解答。
例如 第77题
1function backtrack(n: number, k: number, startIndex: number, path: number[], result: number[][]) {
2 if (path.length === k) {
3 result.push([...path]);
4 return;
5 }
6
7 for (let i = startIndex; i <= n; i++) {
8 path.push(i);
9 backtrack(n, k, i + 1, path, result);
10 path.pop();
11 }
12}
13
14/**
15 * #77, https://leetcode.cn/problems/combinations/
16 */
17export const Combine = (n: number, k: number): number[][] => {
18 const result: number[][] = [];
19 const path: number[] = [];
20 backtrack(n, k, 1, path, result);
21 return result;
22};
- 递归函数的返回值以及参数
一般定义两个全局变量,一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。
还需要一个参数 startIndex, 每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex。 - 回溯函数终止条件
- 剪枝优化
上面题目的回溯函数终止条件为: path.length === k。 循环的最大次数如何确定:
- startIndex 随着循环推移。
- 已经选择的元素个数: path.size();
- 还需要的元素个数为: k - path.size();
- 在集合n中至多要从该起始位置至 n - (k - path.size()) + 1 遍历,后面 (k - path.size - 1) 个元素是不需要遍历的。
1// Problem: Combinations
2// url: https://leetcode.com/problems/combinations/
3#[allow(dead_code)]
4fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
5 let mut result = Vec::new();
6 let mut path = Vec::new();
7 backtracking(n, k, 1, &mut path, &mut result);
8 result
9}
10
11// p2: start point
12// p3: path
13// p4: result
14fn backtracking(p0: i32, p1: i32, p2: i32, p3: &mut Vec<i32>, p4: &mut Vec<Vec<i32>>) {
15 // base case
16 if p1 == 0 {
17 p4.push(p3.clone());
18 return;
19 }
20 // recursive case
21 for i in p2..=p0 {
22 p3.push(i);
23 backtracking(p0, p1 - 1, i + 1, p3, p4);
24 p3.pop();
25 }
26}
1function letterCombinations(digits: string): string[] {
2 const len = digits.length;
3 const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
4 if (!len) {
5 return [];
6 }
7 if (len === 1) {
8 return map[digits].split("");
9 }
10 const ans = [];
11 const path = [];
12
13 function backtracking(n: string, k: number, startIndex: number) {
14 if (path.length === k) {
15 ans.push(path.join(''));
16 return;
17 }
18 for (const v of map[n[startIndex]]) {
19 path.push(v);
20 backtracking(n, k, startIndex + 1);
21 path.pop();
22 }
23 }
24
25 backtracking(digits, len, 0);
26 return ans;
27};
在 javascript 中递归和迭代的效率哪个高
在大多数编程语言中,包括JavaScript,迭代的效率通常会高于递归。
理由如下:
- 递归函数会在内存中创建大量的堆栈帧来存储函数的状态。每一次递归调用都会增加一层堆栈深度,如果递归深度太大,会导致堆栈溢出错误(stack overflow)。而迭代则不会有这种情况。
- 递归调用过程中,如果函数自身存在复杂的操作,比如涉及到大量计算或者数据操作,那么这些操作在每一层递归中都要进行,这也会增加执行的时间。
- JavaScript中的函数调用(包括递归调用)有一定的开销,因为每次函数调用都需要创建新的执行环境、变量对象等。如果函数调用非常频繁,这个开销也会影响效率。而迭代则可以在一个函数执行环境中完成整个循环,不需要频繁的函数调用。
不过也需要注意,递归有其特定的用处,特别是在处理一些特定的数据结构,如树或图时,递归可以让代码更清晰、更易理解。另外,在某些特定的场景,如尾递归优化的环境中,递归的效率可以与迭代相媲美。在ES6中,JavaScript对尾递归做了优化,但是实际的支持情况可能因浏览器的不同而有所差异。