3.4.1. 递归法介绍

3.4.1.1. 递归的基本概念

学习递归算法，主要涉及三个基本概念：递归、递归法、递归调用。它们是三个相互关联但互不相同的概念。

递归，是一个数学上的概念，在描述概念之前先来看两幅图。

这是一组俄罗斯套娃玩具，一个大的娃娃里面套着一个一模一样但是尺寸略小的娃娃，这个略小的娃娃里面还套着一个更小一点的娃娃。这样一层一层的套下去，每次都是一模一样的娃娃，只是尺寸略小，直到最小的一个为止。

这个图就更经典了，这是1900年一位瑞士画家为Droste牌可可粉设计的包装盒。在这个盒子上画着一名护士，手上的托盘里放着一盒同样的Droste可可粉和一杯美味的热巧克力。神奇的是托盘上的那一盒同样的Droste可可粉。因为同样，所以在图中这个盒子上自然也画着同样的内容：一名护士，手上的托盘里放着一盒同样的Droste可可粉和一杯热巧克力……你可以想象这个过程还会如此继续下去，非常神奇。

这就是艺术史上非常著名的第一幅展现了递归效果的画，后来这一类的画作乃至电影电视作品呈现的递归效果，就被称为“Droste效应”，成为一种艺术流派。

上面这两幅图展示了现实生活中的递归现象，类似这样的现象还有许多许多，几乎遍及所有场合。比如雪花边缘的分形结构、比如著名的鬼畜故事从前有座山，山上有座庙，庙里的老和尚对小和尚说：从前有座山，山上有座庙，庙里的老和尚对小和尚说：从前有座山，山上有座庙，庙里的老和尚对小和尚说：……

后来数学家对递归现象进行了深入研究，得到了许多重要的结论和发现，他们对递归下了这样的定义：递归是一种现象，当一物体由和它自身相同或同类型的组成部分构成的时候，就称该物体通过递归进行定义。

数学上的定义总是很抽象，计算机科学家们则利用递归现象归纳出了一套用于设计算法的方法，称为递归法。递归法把大型的复杂问题层层转化为一个或数个与原问题具有相同结构的小问题来求解，层层递归下去直到规模缩小到可以直接求解的程度，得出最小规模问题的解，然后再层层原路返回，用已经得到的小问题的解来反过来构造出大问题的解，直至得到原问题的解。

使用递归法设计的算法就称为递归算法，是最为重要的一类算法。根据前面对递归法的描述可知，一个递归算法由终止条件、递归过程和返回过程三部分组成。

终止条件就是递归结束的条件，当问题规模已经小到可以直接求解时，我们就说递归达到终止条件了，应当结束了。如果一个递归算法没有终止条件，那么就会出现“从前有座山”这样的无限递归错误。

递归过程就是当终止条件还没有达到的时候，问题的规模还不足以直接求解，这时候就需要进一步分解问题，也就是进一步递归下去的过程。在实际编程的时候，递归过程通常用循环结构或者函数的递归调用来实现。

返回过程就是根据小问题的解来构造大问题的解的过程。一般当一次递归到达终止条件后，最小规模问题直接得出解开始，这些小问题的解就要沿着前面递归分解问题的路径原路返回，一路把已经得到的小问题解组合构造成上一层的较大问题的解，如此层层返回，直到回到最开始的原问题，从而构造出原问题的解。

所以我们可以得出递归算法框架的一般形式，所有递归算法都要遵循这样一个框架。在实际编程时，根据所用语言和技术手段的不同，代码可能呈现各种不同的样式，但是算法是唯一不变的。

递归算法的一般框架

\(\text{Recursive}(p):\)

\(\text{IF 终止条件成立 THEN}\)

\(\text{直接计算出结果 }ans\)

\(\text{RETURN }ans\)

\(ans_1 \leftarrow\text{ Recursive}(p_1)\text{ // 用较小规模的数据}p1\text{进行递归求解}\)

\(\vdots\)

\(ans_n \leftarrow\text{ Recursive}(p_n)\text{ // 原问题可能分解为多个较小规模问题}\)

\(\text{使用递归得到的多个小规模问题的解}ans_1,\dots,ans_n\text{构造出原问题的解}ans\)

\(\text{RETURN }ans\)

可以看到，递归算法的框架很简洁。开头第一段是终止条件判断，如果规模已经小到满足终止条件了就直接计算结果并返回。第二段是将问题分解为几个规模较小的问题并直接调用算法本身去求解，这一段对应的是递归过程。可以想象，如果分解下去的子问题的规模仍然不满足终止条件，那么它们也会进一步按照同样的规则分解自己并启动第二轮递归调用，如此循环下去。这是一个层层缩小规模层层递归调用的动态过程，但是写在算法描述或者程序代码里只是一轮递归调用而已。接下来就是把递归调用返回来的小问题的解组合起来构造出原问题的解，其实这也是一个层层返回的动态过程，整个过程是由一系列的 \(\text{RETURN}\)语句串起来的。

那么在实际拿到一个问题的时候，怎么样判断它是不是可以用递归算法呢？一般来说，能够用以下两个属性来定义解的问题具有递归特征，可以用递归法求解：

1、有终止条件：一个或多个简单的基本情况，能直接得到结果。

2、有递归规则：一系列可以让所有其他情况朝向基本情况退化的规则。

例如，可以用递归的方法来定义一个人的长辈：

1、基本情况：父母是长辈。

2、递归规则：长辈的长辈也是长辈。

警告

学习递归算法，有两条原则千万记住：

1. 算法问题常会有多种算法可用，递归算法不一定是最优算法，往往递推会比递归更好（原则一：能用递推就不用递归）。

2. 递归算法常会有多种实现方法，函数递归调用不一定是最好的实现方法，往往用循环会比用递归调用更好，因为函数调用耗时耗内存而且递归层数受内存限制，弄不好就容易爆空间（原则二：能用循环就不要递归调用）。

总之，递归的设计和编程很简单，但调试和分析很麻烦。我们既不要害怕递归，也不要做递归的原教旨主义者。

下面我们来看两个简单的例子，找一找感觉。

3.4.1.2. 计算阶乘

数学中重要的运算阶乘是这样定义的：一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数 \(n\) 的阶乘写作 \(n!\)。

如果要编写一个计算自然数阶乘的函数，事实上一个极其普通的单循环就足够了：

unsigned long long factorial(unsigned long long n)
{
        unsigned long long f = 1;
        while (n) f *= n--;
        return f;
}

除了上面这个通常的定义以外，阶乘还有一个递归的定义。注意观察它的计算公式：\(n!=n\cdot(n-1)\cdot(n-2)\cdots2\cdot1\)。根据阶乘的通常定义，我们知道 \((n-1)!=(n-1)\cdot(n-2)\cdots2\cdot1\)，于是便可以得到阶乘的递归定义：\(n\) 的阶乘等于 \(n\) 乘以 \(n-1\) 的阶乘，0的阶乘等于1。可以用一个公式来表示这个递归定义：

\[\begin{split}n!=\begin{cases}1&,n=0\\n\cdot(n-1)!&,n>0\end{cases}\end{split}\]

根据这样的递归定义，用C++来实现一个递归的算法是非常方便的。因为C++的函数可以自己调用自己，称为函数的递归调用。这是C++实现递归算法最通常的方法，它在实现的时候代码可以做到和算法伪代码或解的数学定义之间在视觉效果上非常一致。

注意

要知道函数的递归调用并不是实现递归算法的唯一方法。比如曾经有过（现在也还有）许多不支持函数递归调用的编程语言，它们就只能用别的方法来实现递归算法。

而且递归调用函数往往不是最好的实现递归算法的方法，因为函数调用有时间和空间上的开销，所以一个程序里递归调用一个函数的层数有限制，不能太多，否则会严重影响性能甚至造成内存超限，俗称“爆栈”。

但是通过函数递归调用来实现递归算法，会使程序的易读性极强，而且往往是代码量也最少的。

让我们看一下怎样用递归的方法来实现阶乘：

unsigned long long fact(unsigned long long n)
{
        if (n == 0) return 1;
        return n * fact(n - 1);      // 这里利用递归调用fact()自己来实现递归
}

可以看出，这个函数的代码和阶乘的递归定义公式几乎是一一对应的“对译”，代码的可读性非常强。实际上，有许多比阶乘复杂得多的问题，如果能找到它们的解的递归求解形式，就可以利用C++函数的递归调用来直观地实现成程序代码，往往这个过程就是一个“对译”的过程。

初学的时候，看懂这样的一个例子，就足以对递归算法和递归调用这些概念有一个直观认识了。再经过一些练习，就可以自己编程解决很多不太难的递归问题了。但是这时候如果深入思考下去，递归调用的深层运行机制到底是怎样的？往往会让人反而越来越陷入迷惑。为了说明递归调用到底是怎样在运作的，许多教材都画了图解进行解释，网上可以查到很多。这里我们采用另一种类似调试的方法，在 fact() 函数进入和返回的时候输出一些说明文字，然后运行起来看看递归调用的整个过程是如何进行的。

#include <cstdio>

typedef unsigned long long ull;

ull fact(ull n)
{
        for (int i = n; i < 5; ++i) putchar(' ');               // 缩进
        printf("fact(%llu) entered\n", n);                      // 提示现在进入了一次调用
        if (n == 0) {
                for (int i = n; i < 5; ++i) putchar(' ');       // 缩进
                printf("return fact(%llu) = 1\n", n);           // 提示返回
                return 1;
        }

        ull f = n * fact(n - 1);
        for (int i = n; i < 5; ++i) putchar(' ');       // 缩进
        printf("return fact(%llu) = %llu\n", n, f);     // 提示返回
        return f;
}

int main()
{
        printf("5! = %llu\n", fact(5));
        return 0;
}

运行的结果是这样的：

fact(5) entered
 fact(4) entered
  fact(3) entered
   fact(2) entered
    fact(1) entered
     fact(0) entered
     return fact(0) = 1
    return fact(1) = 1
   return fact(2) = 2
  return fact(3) = 6
 return fact(4) = 24
return fact(5) = 120
5! = 120

可以看出以下几个特点：

1、只要递归终止条件 \(n=0\) 还没有达到，递归就会沿着 \(5\to4\to3\to2\to1\to0\) 的过程不断地调用下去，直到 \(n=0\)。

2、递归调用和普通的函数调用一样，调用者会停下来等待被调用者返回。如果被调用者的状态没有达到终止递归的条件，它就会进一步再递归调用一次，于是它也成了一个调用者，它也会停下来等着它这一轮的被调用者函数返回，如此不断继续。

3、一旦某一次递归调用时被调用者的状态达到了终止状态，它就会直接求出解并返回上一层，它的上一层调用者于是苏醒过来继续运行，于是再次返回到更上一层的调用者……如此继续，直到回到最初的那个调用者，然后整个过程就结束了。

4、在每一次递归调用发生后，和普通的函数调用一样，C++会给新的那个被调用者创建自己独立的函数运行空间，在里面会根据代码定义生成一套属于它自己的局部变量，这里的 unsigned long long f 就是这样一个局部变量。从调试输出可以看出，每一次调用 fact() 函数，它都有自己的变量 f，相互之间不会有关联影响。

提示

阶乘的递归版并不比普通版更快，占用空间也更大，实用价值几乎没有。但它是最好的递归入门实例，代码清晰易读，使人一目了然，码风从没人爱的循环蝶变成为了简洁优雅的数学公式“对译”。

这就是最简单也最典型的一个递归算法的例子，千万不要嫌弃它简单，请认真地去理解并亲手尝试一下。

3.4.1.3. 寻找最大数

在一个数组中寻找最大的那个数，这也是一个极简单的小算法，我们以前就学过，用一个单循环，从头到尾比较一遍就可以了。可以用一个函数来封装这个功能：

// 寻找数组a的前n个元素中的最大值
int max(int n, int a[])
{
        int m = a[0];
        for (int i = 1; i < n; ++i)
                if (a[i] > m) m = a[i];
        return m;
}

这种方法总共需要比较的次数是n-1次。

另外我们还可以用递归的思路来寻找最大数。我们可以这样想，n个数中的最大值，就是其中任一个数和其余n-1个数的最大值相比的较大者。如果我们每次都取数组的第一个数，和其余的n-1个数中的最大值进行比较，就可以得到这样一个递归过程：

// 递归地寻找数组a的前n个元素中的最大值
int max(int n, int a[])
{
        if (n == 1) return a[0];    // 递归终止条件，当数的数量仅为1个时，最大值就是它自己
        int m = max(n - 1, a + 1);  // n > 1时，递归获取后n-1个数中的最大值
        return m > a[0] ? m : a[0]; // 后n-1个数中的最大值和第1个数比较，大者就是最大值
}

这样的递归算法要进行多少次比较呢？我们不妨也加上调试语句，然后用10个整数来试一试。

#include <cstdio>

int comps = 0;  // 用来记录比较次数

int max(int n, int a[])
{
        if (n == 1) return a[0];
        int m = max(n - 1, a + 1);
        printf("%d: compare %d and %d\n", ++comps, a[0], m); // 每次有比较就输出相关信息
        return m > a[0] ? m : a[0];
}

int main()
{
        int a[10] = { 4, 2, -4, 0, 17, 21, 7, 1, 13, 10 };
        printf("max of the first %d numbers = %d\n", 10, max(10, a));
        return 0;
}

运行上面的程序，可以看到整个过程中发生比较的次数和每一次的两个数，如下：

1: compare 13 and 10
2: compare 1 and 13
3: compare 7 and 13
4: compare 21 and 13
5: compare 17 and 21
6: compare 0 and 21
7: compare -4 and 21
8: compare 2 and 21
9: compare 4 and 21
max of the first 10 numbers = 21

可见，递归的方法并不能减少比较次数，而且由于不断地在调用函数，反而会增加开销。看来用递归的方法来做寻找最大值的工作是有点得不偿失了。实际上从n个数中寻找最大值或者最小值，比较次数最少是n-1次，这是可以用数学方法精确证明的。所以我们可以得到下面这样一条经验：递归并不一定是最好的方法，甚至经常是不太好的方法！可以不递归的就尽量不要递归。

小结和练习

到这里，递归、递归算法和递归调用的基本概念就讲完了。递归是算法设计中非常重要的一种设计技巧，虽然递归往往带来额外的内存和时间开销，但是对于那些符合递归结构的问题，递归往往能非常清晰地勾画出解题思路，从而得到一个简洁优雅的算法。而利用C++的函数递归调用，可以直观地一一对应地把递归算法实现为程序代码。

学习递归的难点不在于设计，而在于分析。往往给出一个具有递归特征的问题后，设计递归算法并不太难。但是如果给出一个递归程序，要读懂它，还原出递归算法是比较困难的。如果要分析递归的过程、时间复杂度等等就更难了。特别是那些不使用递归调用的递归代码，解读和分析会非常困难。

学习递归的另一个难点，就是如何不使用递归调用来实现递归算法。特别是数据规模很大、算法很复杂时，例如大规模的深度优先搜索问题，为了避免函数递归调用造成的额外开销，往往需要改成普通的循环，或者将递归算法改成等价的递推算法。

上面这些问题，在今后几节的学习中我们都会一一讲解和练习。但是在进入更深入的学习之前，首先还是要掌握好最基本的概念和技巧，所以我们留下一个练习：请弄明白上面的递归寻找最大值示例程序为什么会是这样的输出。