MENU

递归详解

2019 年 07 月 20 日 • 阅读: 54 • 算法

递归是一种应用十分广泛的编程技巧,很多数据结构和算法都可用递归实现,如 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 的单步跟踪功能,对于规模较大、递归层次很深的代码,这种方法不太现实,那么怎样方便地调试递归呢?或许回归原始,打印日志是个好方法,此外要尤其注意边界条件和实际参数的传递。

最后编辑于: 2019 年 08 月 02 日