以前我很少写递归，因为我感觉写递归需要灵感，很难复制。

学习了函数式编程后，我发现写递归其实是有套路的。
递归只需要想清楚 2 个问题：

1. 什么情况不需要计算？
2. 大问题怎么变成小问题？

举例

判断数组是否包含某元素

const has = (element, arr) => {};

什么情况不需要计算？
数组为空的时候不需要计算，一定不包含。

const has = (element, arr) => {
  if (arr.length === 0) return false;
};

怎么把大问题变成小问题？
把 arr 的长度减小，向数组为空的情况逼近。
从 arr 中取出第一个元素和 element 比较：

1. 相同：返回 true。
2. 不相同：求解更小的问题。

const has = (element, arr) => {
  if (arr.length === 0) return false;
  else if (arr[0] === element) return true;
  else return has(element, arr.slice(1));
};

删除数组的某个元素

const del = (element, arr) => {};

什么情况不需要计算？
数组为空的时候不需要计算，返回空数组。

const del = (element, arr) => {
  if (arr.length === 0) return [];
};

怎么把大问题变成小问题？
把 arr 的长度减小，向空数组的情况逼近。
从 arr 中取出第一个元素和 element 比较：

1. 相同：返回数组余下元素。
2. 不相同：留下该元素，再求解更小的问题。

const del = (element, arr) => {
  if (arr.length === 0) return [];
  else if (arr[0] === element) return arr.slice(1);
  else return [arr[0], ...del(element, arr.slice(1))];
};

阶乘、斐波纳切

阶乘、斐波纳切用递归来写也是这个套路，代码结构都是一样的。

先列出不需要计算的情况，再写大问题和小问题的转换关系。

const factorial = n => {
  if (n === 1) return 1;
  else return n * factorial(n - 1);
};

const fibonacci = n => {
  if (n === 1) return 1;
  else if (n === 2) return 1;
  else return fibonacci(n - 1) + fibonacci(n - 2);
};

小孩子的加法

我观察过小孩子用数数的方式做加法，过程是这样的：

3 颗糖 加 2 颗糖 是几颗糖？

他会把 3 颗糖放左边，2 颗糖放右边。
从右边拿 1 颗糖到左边，数 4，
再从右边拿 1 颗糖到左边，数 5，
这时候右边没了，得出有 5 颗糖。

这其实也是递归的思路。

const add = (m, n) => {};

不需要计算的情况是 当 n = 0 时，结果就是 m。

const add = (m, n) => {
  if (n === 0) return m;
};

把问题向 n = 0 逼近：

const add = (m, n) => {
  if (n === 0) return m;
  else return add(m + 1, n - 1);
};

当然 m = 0 也是不需要计算的情况，选择 m = 0 还是 n = 0 决定了大问题转成小问题的方向。

Continuation Passing Style

const add1 = m => m + 1;

把 add1 的返回结果乘 2，我们通常这么写

add1(5) * 2;

如果用 Continuation Passing Style 来写，add1 多加一个参数 continuation，它是一个函数，表示对结果的后续操作，
那么 add1 的返回结果乘 2，可以这样写

const add1 = (m, continuation) => continuation(m + 1);
add1(5, x => x * 2);

用 Continuation Passing Style 来写写递归。

阶乘

const factorial = (n, continuation) => {
  if (n === 1) return continuation(1);
  else return factorial(n - 1, x => continuation(n * x));
};

如果 n === 1，结果就是 1，把结果交给 continuation；
如果 n > 1，计算 n - 1 的阶乘，把 n - 1 阶乘的结果 x 乘 n，交给 continuation。

这个 factorial 函数该怎么调用呢？
continuation 可以传 x => x，这个函数接收什么就返回什么。

factorial(5, x => x);

和之前的写法对比一下：

const factorial = n => {
  if (n === 1) return 1;
  else return n * factorial(n - 1);
};

之前的写法中，递归调用 factorial(n - 1) 不是函数的最后一步，还需要乘 n。
因此编译器必须保留堆栈。

const factorial = (n, continuation) => {
  if (n === 1) return continuation(1);
  else return factorial(n - 1, x => continuation(n * x));
};

新写法中，递归调用 factorial(n - 1, x => continuation(n * x)) 是函数的最后一步。
做了尾递归优化的编译器会不保留堆栈，从而不怕堆栈深度的限制。
也就是说：可以通过 Continuation Passing Style， 把递归变成尾递归。

斐波纳切

const fibonacci = (n, continuation) => {
  if (n === 1) return continuation(1);
  else if (n === 2) return continuation(1);
  else return fibonacci(n - 1, x => fibonacci(n - 2, y => continuation(x + y)));
};

如果 n === 1，结果是 1，把结果交给 continuation；
如果 n === 2，结果是 1，把结果交给 continuation；
如果 n > 2，计算 n - 1 的结果 x，再计算 n - 2 的结果 y，把 x + y 交给 continuation。

Continuation Passing Style 可以把递归变成尾递归，但并不是说用了 Continuation Passing Style 的递归就是尾递归。

像这么写，就不是尾递归。

const fibonacci = (n, continuation) => {
  if (n === 1) return continuation(1);
  else if (n === 2) return continuation(1);
  else return fibonacci(n - 1, x => continuation(fibonacci(n - 2, y => x + y)));
};

x => continuation(fibonacci(n - 2, y => x + y));

因为 fibonacci 不是函数的最后一步，最后一步是 continuation(fibonacci_result)。