递归的三种形式

Published by powerfulyang on Jul 3, 2022

Memorization

将计算结果保存，避免重复计算。

Divide and Conquer

分治，将大问题分解成小问题，各个击破，然后将小问题组合起来。

  1. Divide
  2. Conquer
  3. Combine

Backtracking

回溯法用来解决 N 个 for 循环的问题
不断试错，知错就改。类似于暴力搜索, 但是会剪枝优化。 一般要求返回所有满足条件的解答。

例如 第77题

typescript
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。 循环的最大次数如何确定:

  1. startIndex 随着循环推移。
  2. 已经选择的元素个数: path.size();
  3. 还需要的元素个数为: k - path.size();
  4. 在集合n中至多要从该起始位置至 n - (k - path.size()) + 1 遍历，后面 (k - path.size - 1) 个元素是不需要遍历的。
rust
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}

电话号码的字母组合

typescript
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，迭代的效率通常会高于递归。

理由如下：

  1. 递归函数会在内存中创建大量的堆栈帧来存储函数的状态。每一次递归调用都会增加一层堆栈深度，如果递归深度太大，会导致堆栈溢出错误（stack overflow）。而迭代则不会有这种情况。
  2. 递归调用过程中，如果函数自身存在复杂的操作，比如涉及到大量计算或者数据操作，那么这些操作在每一层递归中都要进行，这也会增加执行的时间。
  3. JavaScript中的函数调用（包括递归调用）有一定的开销，因为每次函数调用都需要创建新的执行环境、变量对象等。如果函数调用非常频繁，这个开销也会影响效率。而迭代则可以在一个函数执行环境中完成整个循环，不需要频繁的函数调用。

不过也需要注意，递归有其特定的用处，特别是在处理一些特定的数据结构，如树或图时，递归可以让代码更清晰、更易理解。另外，在某些特定的场景，如尾递归优化的环境中，递归的效率可以与迭代相媲美。在ES6中，JavaScript对尾递归做了优化，但是实际的支持情况可能因浏览器的不同而有所差异。