基础 递归

从具体到抽象

斐波那契数列

写一个函数，输入 n，求斐波那契 (Fibonacci) 数列的第 n 项 (即 F(N))。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7 (1000000007)，如计算初始结果为：1000000008，请返回 1。

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

迭代版本

function fib(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  var arr = [0, 1];
  for (var i = 2; i <= n; i++) {
    // 每一轮对其取模和最后再取模的结果相同
    arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
  }
  return arr[i - 1];
};

爬楼梯

爬楼梯问题是一个经典的动态规划问题，通常描述为：你正在爬楼梯，需要到达第 n 级台阶。每次你可以选择爬 1 级或 2 级台阶。问有多少种不同的方法可以到达第 n 级台阶。

用数学语言表示就是： [ f(n) = f(n-1) + f(n-2) ]

function climbStairs(n) {
    // 基本情况：爬1级台阶需要1种方法，爬2级台阶需要2种方法
    if (n === 1) return 1;
    if (n === 2) return 2;

    // 递归关系：爬n级台阶的方法数等于爬n-1级台阶的方法数加上爬n-2级台阶的方法数
    return climbStairs(n - 1) + climbStairs(n - 2);
}

这个递归解法虽然简洁，但效率不高，因为它会重复计算很多子问题。对于较大的 n 值，使用记忆化搜索（memoization）或动态规划来优化性能会更高效。以下是使用记忆化的改进版本：

function climbStairs(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n === 1) return 1;
    if (n === 2) return 2;

    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    return memo[n];
}

汉诺塔

据说创世纪时 Benares 有一座波罗教塔，是由三支钻石棒 (Pag) 所支撑，开始时神在第一根棒上放置 64 个由上至下依由小至大排列的金盘 (Disc)，并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。

汉诺塔问题的主要目的是演示递归算法的概念和如何通过分解问题来解决复杂问题。

// 递推公式，移动n个盘子时，将其分为上面n-1个和第n个盘子两部分移动

// 第一步，将上面n-1个盘子从X经过Z放到Y上，YZ互换后，问题退化
// 第二步，将剩下的第n个盘子从X放到Z上
// 第三步，将剩下n-1个盘子从Y经过X放到Z上，XY互换后，问题退化

function hanoi(n, A, B, C) {
  if (n === 1) {
    console.log(`Move sheet ${n} from ${A} to ${C} `); // 操作
  } else {
    hanoi(n - 1, A, C, B);
    console.log(`Move sheet ${n} from ${A} to ${C} `); // 操作
    hanoi(n - 1, B, A, C);
  }
}

hanoi(4, "A", "B", "C");
// Move sheet 1 from A to C
// Move sheet 2 from A to B
// Move sheet 1 from C to B
// Move sheet 3 from A to C
// Move sheet 1 from B to A
// Move sheet 2 from B to C
// Move sheet 1 from A to C

组合生成

组合生成问题涉及生成给定元素集的所有可能组合。例如，给定一个集合 ( {a, b, c} )，可以生成所有长度为2的子集：( {a, b}, {a, c}, {b, c} )。

function generateCombinations(elements, k) {
    if (k === 0) return [[]];
    const combinations = [];
    for (let i = 0; i < elements.length; i++) {
        const firstElement = elements[i];
        const remainingElements = elements.slice(i + 1);
        for (const combination of generateCombinations(remainingElements, k - 1)) {
            combinations.push([firstElement].concat(combination));
        }
    }
    return combinations;
}

console.log(generateCombinations(['a', 'b', 'c'], 2)); // 输出: [['a', 'b'], ['a', 'c'], ['b', 'c']]

排列生成

排列生成问题涉及生成给定元素集的所有可能排列。例如，给定一个集合 ( {a, b, c} )，可以生成所有长度为3的排列：( (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a) )。

function generatePermutations(elements) {
    if (elements.length === 0) return [[]];
    const permutations = [];
    for (let i = 0; i < elements.length; i++) {
        const firstElement = elements[i];
        const remainingElements = elements.slice(0, i).concat(elements.slice(i + 1));
        for (const permutation of generatePermutations(remainingElements)) {
            permutations.push([firstElement].concat(permutation));
        }
    }
    return permutations;
}

console.log(generatePermutations(['a', 'b', 'c'])); 
// 输出: [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]