递归详解

递归是一种应用十分广泛的编程技巧，很多数据结构和算法都可用递归实现，如 DFS，二叉树的前中后序遍历等。

递归问题的必要条件

先看一个例子，假设要上 n 阶楼梯，上楼者每次只能跨 1 阶或两阶，问有多少种走法？

记上 n 阶台阶的走法数为 f(n)，当楼梯只有 1 阶时，只有 1 种走法，即 f(1) = 1。当楼梯有 2 阶时，要么一步走完，要么第一步走 1 阶，第二步必然是 1 阶，总共 2 种走法，即 f(2) = 2。

当 n>2 时，到达 n 阶只可能来自 n-1 和 n-2 阶梯，所以 f(n) = f(n-1) + f(n-2)。

有了上面的递推公式，问题就可以解决了，比如楼梯有 7 阶，先往前递推 f(7) = f(6) + f(5)，f(6) = f(5) + f(4)，f(5) = f(4) + f(3)，f(4)= f(3) + f(2)，f(3) = f(2) + f(1)。再逆序计算，f(1) = 1，f(2) = 2，f(3) = 3，f(4) = 5，f(5) = 8，f(6) = 13，f(7) = 21。只要你愿意并且时间允许，任意阶楼梯的走法都能计算出来。

总结一下上述问题的解决过程，首先我们计算出了数据规模最少的两种情况，f(1) = 1，f(2) = 2，不妨称它们为 边界条件。随后我们将问题 分类，发现每类都是规模更小，但问题相同的子问题，基于此，我们找到了 递推公式。最后，根据递推公式不断往前递推，到达边界条件后逆序计算回去，问题便得到了解决，解决该问题的过程就是 递归。

我们发现，使用递归思想会使问题变得简单，那么哪些问题可以用递归解决呢？答案是问题必须满足以下三点：

• 原问题可以分解成几个数据规模更小的子问题
• 原问题与子问题除了数据规模不同，实际上是相同问题
• 能够找到边界条件

下面是楼梯问题的编码：

int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

使用递归编码是不是非常简洁直观，我们再通过一个例子练习一下递归思想。有一组数，如 3，2，6，7，5，4，如何求它们的最大值？

第一步，分解问题。拿出第一个数 3，如果已经知道剩余序列 2，6，7，5，4 的最大值是 7，那么问题就变为 3 和 7 比较大小。也就是问题可以分解为第一个数和后面 n-1 个数地最大值比较大小。

第二步，考察子问题，寻找递推公式。不难发现求后 n-1 个数的最大值和求 n 个数的最大值是同一问题，仅仅是数据规模变小了。记 n 个数的最大值为 f(n)，两个数的最大值为 max(a, b)，那么 f(n) = max(a[0], f(n-1))。

第三步，寻找边界条件。考虑只有两个数 m 和 n。如果 m>n，m 就是最大值，反之，n 是最大值。

我们发现求一组数的最大值满足上述三个条件，可以用递归解决，下面是它的编码：

int max(int a, int b) {
    return a > b ? a : b;
}

//  head 指向剩余序列首元素，第一次调用时传 0
int f(int a[], int head) {
    if (a.length - 2 == head) return max(a[head], a[head+1]);
    return max(a[head], f(a, head+1));
}

再看一个例子，一个人拉着鸭子去村庄卖，每经过一个村子卖掉所拉鸭子的一半加一只。当他经过第七个村子后还剩两只鸭子，问他出发时带了多少只？

从题干可知，经过一个村子后剩余的鸭子数与上一村子有关，它们之间存在明显的递推关系。记经过 n 个村子后剩 f(n) 只鸭子，那么经过第 n+1 个村子后剩 f(n+1) 只，根据题意有 f(n+1) = f(n) - [f(n)/2 + 1] = f(n)/2 - 1。因为要求 f(n)，所以把它移到等式左边，有 f(n) = [f(n+1)+1]*2，这就是递推公式。

题干还说，经过第 7 个村子后，剩余 2 只，也就是 f(7) = 2，这便是边界条件。题目要求的是出发时带了几只，也就是 f(0)，根据递推公式，每次计算都会靠近边界条件 f(7)，程序可以正常退出，下面是问题编码：

// 求 f(0)
int f(int n) {
    if (n == 7) return 2;
    return 2 * (f(n + 1) + 1);
}

你是否有疑问，将 f(n) 转化为求 f(n+1) 不是使数据规模变大了吗？其实不然，因为问题是求 f(0)，边界条件是 f(7)，n 越大，越靠近 7，计算过程越少，也就是数据规模越小。

简化递归思考过程

计算机擅长做重复的事情，所以递归正和它的胃口。而人脑更喜好平铺直叙的思维方式，当我们看到递归时，总想把递归过程展开，一层一层往下调，再一层一层返回，试图搞清楚计算机每一步是如何执行的，这样便很容易被绕进去，其实这是一个思维误区。

递归的难点是如何找到递推公式，尤其是一个问题要分解成多个子问题时。对此，你可以假设子问题已经全部得到解决。例如问题 A 可以分解为 B、C、D 三个子问题，你应该假设 B、C、D 都已得到解决，在此基础上思考如何解决 A。也就是仅仅思考原问题 A 与子问题 B、C、D 两层间的关系，不要考虑 A 与 B、C、D 的子问题之间的关系。

递归代码的缺陷及解决方法

堆栈溢出

在 栈及其基本应用 中我们提到，函数调用会使用栈来保存临时变量。每次递归调用，都会将参数等临时变量封装为栈帧压入内存中的函数调用栈，等待执行返回后才出栈。由于内存是有限的，所以系统栈或虚拟机栈也是有限的，如果递归数据规模很大，调用层次很深，一直压栈就会产生堆栈溢出。堆栈溢出会造成程序崩溃，如果是系统组件，就会引发系统崩溃，后果非常严重。

如何避免堆栈溢出呢？方法之一是限制递归深度，比如以下代码，递归到第 1000 层时直接抛异常给调用者处理：

int depth = 1;
int f(int n) throws Exception {
    if (depth++ > 1000) throw new Exception();
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);
}

但以上做法并不完美，理论上，最佳递归深度应该根据当前线程剩余栈空间设定，但剩余空间事先无法计算，如果实时计算，代码会非常复杂。因此，这种方法适合递归最大深度已知且比较小的情况，例如我们知道 50 次便可完成计算，如果递归了 100 次说明发生了错误，应该立即停止递归。

重复计算

递归往往会发生重复计算问题，以上述楼梯问题为例，它的递推公式为 f(n) = f(n - 1) + f(n - 2)，边界条件为 f(1) = 1，f(2) = 2。下面是计算 6 层阶梯要进行的递归计算过程。

                f(6)
               /    \
              /      \ 
             /        \
            /          \
        f(5)            f(4)
       /   \             /\
      /     \           /  \
    f(4)     f(3)     f(3) f(2)
   /    \     / \     /\
  /      \   /   \   /  \
 f(3)  f(2) f(2)f(1)f(2)f(1)
  / \
 /   \
f(2)f(1) 

可以看到，f(3) 计算了 3 次，f(4) 计算了 2 次。如果数据规模变大，如计算 f(100)，那么重复计算的损耗将十分可观。为了避免重复计算，就要将已计算的结果保存，并且需要在 O(1) 时间取出它，散列表刚好满足这种需求，需要注意的是，引入散列表会增加空间复杂度，这是一种以空间换时间的做法。以下是示例代码：

Map<Integer, Integer> map = new HashMap<>();
int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (map.containsKey(n)) return (int) map.get(n);
    int ret = f(n - 1) + f(n - 2);
    map.put(n, ret);
    return ret;
}

时空复杂度高

除了重复计算带来的高时间复杂度，递归函数调用本身就会积聚可观的时间成本。从空间复杂度考虑，每次递归调用都要在内存栈中保存现场，这无疑占用了很大的额外空间，如上述楼梯问题的空间复杂度就是 O(n)。

递归与迭代的转换

递归有利有弊，它的表达力很强，代码也十分简洁。同时，递归的空间复杂度很高，还存在堆栈溢出、重复计算、函数调用耗时等问题，需要要根据实际需求决定是否使用递归。有些情况下，将递归转换为迭代，往往效率更高，例如上楼梯的例子，转换的诀窍是模拟递归中归的过程。

int f(int n) {
    if (n == 1 || n == 2) return n;
    int prevPrev = 1;
    int prev = 2;
    int ret = 0;
    for (int i = 3; i <= n; i++) {
        ret = prevPrev + prev;
        prevPrev = prev;
        prev = ret;
    }
    return ret;
}

求数组最大值的例子：

int f(int[] a) {
    int max = a[a.length - 1];
    for (int i = a.length - 2; i >= 0; i--)
        if (a[i] > max) max = a[i];
    return max;
}

卖鸭子的例子：

int f() {
    int next = 2;
    int ret = 0;
    for (int i = 6; i >= 0; i--) {
        ret = 2 * (next + 1);
        next = ret;
    }
    return ret;
}

是否所有递归都能转换为迭代呢？理论上说，的确如此，但某些转换并不能提高效率。我们知道，递归本身就是借助栈实现的，只不过这些栈是系统或虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，并手动模拟入栈，出栈的过程，所有递归代码都能转换成看上去非递归的形式。但这种转换的本质并没有改变，实际上是手动递归，不能解决递归本身存在的问题，并且会增加实现的复杂度。

我们再通过一个例子复习递归。很多 APP 都有推荐注册返佣金的功能，如何找到某个用户的最终推荐人呢？

一般数据库都会记录用户的直接推荐人，例如 A 是 B 的推荐人，B 又是 C 的推荐人，那么 A 就是 C 的最终推荐人。我们只需查出用户的上级推荐人，再查上级推荐人的上级，直到某个用户没有推荐人，它就是要找的最终推荐人。查当前用户的推荐人和查推荐人的推荐人其实是同一个问题，都是查出直接推荐人。边界条件是某个用户没有推荐人，下面是实现代码：

String getRootReferrerId(String userId) {
    // getReferrerId() 会进行数据库查询
    String referrerId = getReferrerId();
    if (referrerId == null) return userId;
    return getRootReferrerId(referrerId);
}

当然，可以通过迭代实现：

String getRootReferrerId(String userId) {
    String referrerId = getReferrerId(userId);
    if (referrerId == null) return userId;
    while (userId != null) {
        referrerId = getReferrerId(userId);
        userId = referrerId;
    }
    return referrerId;
}

实际上，上述代码存在两个问题。第一、如果递归很深，可能发生堆栈溢出。其次，如果数据库中含有脏数据，可能发生无限递归。例如，测试工程师插入了以下数据，A 的推荐人是 B，B 的推荐人是 C，C 的推荐人又是 A，这样便会发生无限递归，对于循环代码就会发生无限循环。

调试

我们平时调试代码喜欢使用 IDE 的单步跟踪功能，对于规模较大、递归层次很深的代码，这种方法不太现实，那么怎样方便地调试递归呢？或许回归原始，打印日志是个好方法，此外要尤其注意边界条件和实际参数的传递。