什么是递归

小时候，我们都听过下面这则故事：

从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？「从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？『从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？…』」

这个故事自己套着自己，没完没了，像是某种特征在不断地重复，这就是递归了。

在计算机科学里，递归指的是一种通过重复将问题分解为同类的子问题而解决问题的方法。套用程序的概念，就是函数执行过程中直接或间接地调用自身。

用递归来解决问题

由递归的概念可知，如果某个问题有一些自相似的特征，可以分解为子问题，那么它就可以被递归定义。如果问题被递归定义了，也差不多解决了。

我们来看一个具体例子：

假设现在有 5 个人、5 个座位，那这几个人的位置分布情况有几种。我们先来列举一下：

1
2
3
4
5

第 1 个人：有 5 种选择
第 2 个人：有 (5 - 1) 种选择
第 3 个人：有 (5 - 2) 种选择
第 4 个人：有 (5 - 3) 种选择
第 5 个人：有 (5 - 4) 种选择

那么 5 个人总共的选择数是：

1

5 * (5 - 1) * (5 - 2) * (5 - 3) * (5 - 4);

同理，如果总共是 n 个人、n 个座位，那么所有可能的情况数 f(n) 可以表示为：

1

f(n) = n * (n - 1) * … * 2 * 1

这里的未知数 n 有无数种可能，我们不可能把所有的情况都列举出来，然后得到结果。要解决这样的问题，就要运用递归的思想，找到各个情况的共同模式，切分成小的有限的问题，然后尝试着把它描述出来。

我们先把 n <= 5 的情况列举出来：

1
2
3
4
5

f(1) = 1;
f(2) = 2 * 1;
f(3) = 3 * 2 * 1;
f(4) = 4 * 3 * 2 * 1;
f(5) = 5 * 4 * 3 * 2 * 1;

通过对比可以观察到一个现象：

1
2
3
4
5

f(1) = 1;
f(2) = 2 * f(1);
f(3) = 3 * f(2);
f(4) = 4 * f(3);
f(5) = 5 * f(4);

我们找到了一个共同模式，描述出来就是，对于 f(n) 来说，它的值是参数 n 和前一步的值的乘积，前一步和后一步的参数之间相差 1，所以我们很自然就想到用这个 1 做切分，即：

1

f(n) = n * f(n - 1);

这样我们就定义了这个函数 f，它会在执行的过程中调用自己，又称为递归函数，用 JavaScript 实现就是这样：

1
2
3

var f = function (n) {
 return n * f(n - 1);
};

简单分析一下，这个函数每执行一次，参数 n 就少 1，最终它会到达 0，之后还会进一步到负数，看起来好像永远都得不到结果。

我们回到命题，当 n 到达 0 时，f(0) 指的就是「在 0 个人、0 个座位时的位置分布情况」，没有意义，是 Empty Product，值为 1。而 n 是负数时就更没有意义了，所以 n 应该是一个自然数：

1
2

f(0) = 1;
f(n) = n * f(n - 1);

这里的 n = 0 就是递归函数 f 的一个临界条件，当达到临界条件时，递归函数继续执行没有意义，此时递归结束。在定义递归函数的时候，设定合适的临界条件很重要，否则容易陷入死循环。

相应的，我们的代码也要改变：

1
2
3
4

var f = function (n) {
 if (n === 0) return 1;
 return n * f(n - 1);
};

由此，我们就通过定义递归函数 f 描述了这个问题，对于任意的自然数 n，我们只需执行 f(n) 就可以得到答案。

用递归的思路来解决问题，并不是写出具体的求解步骤，而是试着把问题描述出来，考虑有哪些共同模式，怎么切分，何处结束，以及何处执行递归。

递归函数的优化

当 n = 5 时，我们把上面这个函数完整的执行过程模拟出来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

f(5);
5 * f(4);
5 * (4 * f(3));
5 * (4 * (3 * f(2)));
5 * (4 * (3 * (2 * f(1))));
5 * (4 * (3 * (2 * (1 * f(0)))));
5 * (4 * (3 * (2 * (1 * 1))));
5 * (4 * (3 * (2 * 1)));
5 * (4 * (3 * 2));
5 * (4 * 6);
5 * 24;
120;

我们可以看到，随着 f(5) 这个函数的执行，需要记录的中间状态的数目一直在变，先增后减。在空间消耗上，表现就是栈先累积后收缩，整个计算过程空间复杂度是 O(n)，当 n 很大的时候会 Stack Overflow 。

我们思考一下另一种方案，刚才的执行是从 n 开始，一步步计算，直到临界条件 0 为止。现在试着倒过来，由 1 开始，一步步计算，直到 n 为止，当然，此时的临界条件也相应的变为「超过 n」。

实现起来应该就是这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

var f = function (n) {
 return f2(n, 1, 1);
};
var f2 = function (n, i, result) {
 if (i > n) {
 return result;
 } else {
 return f2(n, i + 1, result * i);
 }
};

我们引入了另一个函数 f2 来完成从 1 到 n 的递归。函数 f2 在尾位置（函数执行的最后）调用自身，这样的递归称为尾递归。

不少编程语言（包括 ES6）都支持对这样的函数进行空间优化，也叫尾递归优化。

具体是怎么进行尾递归优化的呢？

我们回顾一下函数 f2 的定义，因为函数 f2 每次执行的最后是函数调用，而下一步执行所需要的状态都是通过参数传递的，那么当前栈就可以清空被重用。比如，在计算第 3 步的时候，之前的第 1 步、第 2 步的中间状态都不需要了，只保留第 3 步执行需要的参数就行。

我们把优化后的步骤列出来：

1
2
3
4
5
6
7
8

f(5);
f2(5, 1, 1);
f2(5, 2, 1);
f2(5, 3, 2);
f2(5, 4, 6);
f2(5, 5, 24);
f2(5, 6, 120);
120;

可以看出，这种方案随着计算的增加，消耗的空间一直不变，占用恒量的内存，和迭代程序一样，它的空间复杂度是 O(1)。

所以经过尾递归优化后，使得递归计算可以跟 while、for 等迭代式计算的效率基本相当。

参考

• 谈谈递归