基础 递归

从具体到抽象

斐波那契数

写一个函数，输入 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。

var fib = function (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];
};

爬楼梯

汉诺塔

据说创世纪时 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