本章学习目标

●       某些情况下，一个子任务只是大任务的简单版本。能够识别出这种情况，并能设计出针对这些问题的递归解决方案。

●       绘制运行时堆栈图，从而跟踪递归调用。

●       能够找到有效的变量表达式和临界值，从而证明一个递归函数不是无穷递归的。

●       利用归纳法证明递归函数满足它的前置条件/后置条件协议。

在自顶向下的设计过程中，我们经常会遇到一个非常值得注意的情况：要解决的子任务只不过是在开始时打算解决的相同问题的简单版本。实际上，这种情况经常发生，以至于有经验的程序员在设计过程中总是期望在一开始时就能找到大问题的简单版本。这种期望称为递归思想(recursive thinking)。像C++这样的编程语言支持递归思想，使得函数的实现能够调用它自己。在这种情况下，就称函数使用了递归(recursion)。

在本章中，我们首先会尽力识别适合递归思想的各种情况。同时，我们还将讨论C++中的递归，包括怎样将它用于实现递归设计以及实现递归函数执行过程中的各种机制。

9.1  递归函数

9.1.1  递归思想的第一个例子

下面以一个例子来开始递归的讨论。考虑这个任务：在屏幕上以十进制形式输出一个非负整数，并且要求所有位纵向显示在屏幕上。举例来说，数字1234应该显示如下：

1

2

3

4

此问题有一个非常简单的版本：如果整数只有一位，那么可以直接输出该位。但如果要输出的数字不只一位，解决方法就不那么显而易见了，所以我们可以将这个问题分解成两个子任务：(1)纵向输出除最后一位之外其他所有的位；(2)然后输出最后一位。例如，如果数字是1234，那么第一步应该输出：

1

2

3

第二步将输出最后一位4。

有多种因素会影响我们对这两个步骤做出选择，一个因素是如何以简单的方式提供所需的数据。举例来说，如果输入的数字是1234，第一步需要的数据是123，这可以很容易地表示为1234/10(因为整数除以10后会产生一个商，保留这个商，丢弃余数)。通常，如果整数称为number，而且number不只一位，那么第一步就是纵向输出number/10的位。第二步也同样简单：只需要输出number的最后一位，这可以很容易地表示为number%10(也就是number除以10得到的余数)。对于分解问题的其他方式，像number/10和number%10之类的简单表达式不是那么容易就能找出来(例如第一步只输出第一位，然后在第二步输出其余的位)。

上述解决方法的伪代码如下所示：

// 纵向输出一个非负数字的各个位

if (number只有一位)

    输出这一位。

else

{

    纵向输出number/10的位。

    输出number%10唯一的位。

}

我们对递归的认识此时应该会更深一步：上述方法中的一个步骤—— 纵向输出number/10的位—— 是“纵向输出number的位”这个问题的一个比较简单的实例。它之所以简单，是因为number/10比number少了一位。这一步可以通过递归调用纵向输出数字的函数来实现。此递归调用函数的实现如图9-1所示。在这个函数中，使用unsigned int数据类型代替普通的int。两者的不同之处在于unsigned int不会是负数，这恰好满足函数输出非负整数的需求。

稍后我们将会看到递归调用函数的具体实现体制，例如write_vertical(1234)。但是，首先还有两点需要解释：

(1) 停止条件 如果问题很简单，就可以不用递归调用来解决。在write_vertical函数中，当number只有一位时，就会发生这种情况。这种没有任何递归调用的情况称为停止条件(stopping case)或基本条件(base case)。在图9-1中，write_vertical的停止条件由下面这两行代码实现：

if (number < 10)

    cout << number << endl;     // Write the one digit.

(2) 递归调用 在图9-1中，函数write_vertical执行了一个递归调用。该递归调用是下列代码中有阴影的语句：

else

{

    write_vertical(number/10);  // Write all but the last digit.

    cout<<number%10<<end;   // Write the last digit.

}

这是write_vertical函数调用自身的一个实例，用于解决比较简单的问题，即输出除最后一位之外的所有位。

void write_vertical(unsigned int number)

// Postcondition: The digits of number have been written, stacked vertically.

// Library facilities used: iostream.h

{

    if (number < 10)

        cout << number << endl;  // Write the one digit.

    else

    {

        write_vertical(number/10);          // Write all but the last digit.

        cout << number % 10 << endl;       // Write the last digit.

    }

}

write_vertical(1234)的示范结果

1

2

3

图9-1  write_vertical函数

9.1.2  跟踪递归调用

在类似于write_vertical(3)这样的函数调用中，具体的过程是怎样的呢？第一步是把实参3复制给函数的形参number。这是函数调用中处理值参数的基本方法：实参为形参提供初始值。

一旦形参有了初始值，就开始执行函数的代码。由于3比10小，所以if语句中的布尔表达式的值为true。因此在这种情况下，可以很容易地看出函数只是输出3，而不再做其他的工作。

接下来，尝试另一个参数，该参数会使函数进入if语句的else部分，例如下面的函数调用：

write_vertical(37);

当函数被调用时，number的值被设置为等于37，然后执行代码。因为37不小于10，所以else部分的两个语句都得到执行。下面是第一个语句：

write_vertical(number/10);  // Write all but the last digit.

在这个语句中，(number/10)是(37/10)，结果等于3。所以，这个函数调用是write_vertical(3)。前面已经分析了write_vertical(3)的动作：在单独的一行中输出3。在write_vertical这个函数调用彻底完成之后，执行else部分的第二行：

cout << number % 10 << endl;

这行代码只是输出number%10的值。在本例中，number是37，所以这条语句输出数字7。else部分两行代码的所有输出结果是：

3

7

函数write_vertical使用了递归。然而在计算函数调用write_vertical(37)时，并没有做任何新的或者是其他不同的工作。我们只是把它和其他的函数调用一样对待。这里只是简单地替换了number的实参，然后执行代码。在到达递归调用write_vertical(3)时，只是简单地一次次重复这个过程。

9.1.3  编程示例：write_vertical的一个扩展

下面将write_vertical扩展为一个功能更加强大的函数super_write_vertical，该函数能够处理包括负数在内的所有整数。当输入一个负数时，新函数在输出的第一行首先输出负号，然后再输出其他的位。举例来说：

super_write_vertical(-361)

此函数的输出如下，其中的第一行是一个负号：

-

3

6

1

如何处理一个负数呢？第一步看起来很清楚：输出负号。在这之后，必须输出number的各个位，这等同于输出abs(number)的各个位(abs函数是源自<cstdlib>中的“绝对值”函数。该函数保持正数不发生变化，而使负数去掉前面的负号)。因此，super_write_vertical的伪代码是原始伪代码的扩展：

if (number是一个负数)

{

    输出一个负号。

    纵向输出abs(number)的各个位。

}

else if (number只有一位)

    输出这一位。

else

{

    纵向输出number/10的位。

    输出number%10唯一的一位。

}

如果采用递归思想去思考，我们就会发现“纵向输出abs(number)的各个位”这一步只是原来问题的一个简单版本(之所以简单，是因为不需要输出负号)。这就指出了图9-2中的实现，其中包含两个递归调用：第一个调用针对输出abs(number)各个位这种新情况，第二个调用针对原来的输出number/10各个位的情况。图中的一些代码添加了高亮的注释，标明了两个特定的位置：“Spot #1”和“Spot #2”，这有助于更清楚地观察递归，。

void super_write_vertical(int number)

// Postcondition: The digits of the number have been written, stacked

// vertically.

// If number is negative, then a negative sign appears on top.

// Library facilities used: iostream(using namespace std)

{

    if (number < 0)

    {

        cout << '-' << endl;                   // print a negative sign

        super_write_vertical(abs(number));   // abs computes absolute value.

        || This is Spot #1 referred to in the text.

    }

    else if (number < 10)

        cout << number << endl;              // Write the one digit.

    else

    {

        super_write_vertical(number/10);   // Write all but the last digit.

        || This is Spot #2 referred to in the text.

        cout << number % 10 << endl;         // Write the last digit.

    }

}

super_write_vertical(-361)的示范结果

-

3

6

图9-2  super_write_vertical函数

9.1.4  深入分析递归

计算机利用下面的方式跟踪函数调用：当遇到函数调用时，计算机首先保存一些信息，从而使得在函数执行完之后，计算机能够根据这些信息返回到正确的位置。计算机还为被调用函数的形参和它使用的任何局部变量提供内存。接下来，实参的值传递给形参，并开始执行被调用函数的代码。

如果执行过程中遇到对另一个函数的调用—— 递归或者是其他函数—— 那么第一个函数的计算就会暂时停止。这是因为第二个函数调用必须在第一个函数调用继续执行之前先执行。计算机又会保存一些信息，这些信息准确地表示了在第二个函数调用完成之后第一个函数调用应该在什么地方恢复执行。在为第二个函数的参数和局部变量分配内存之后，开始执行第二个函数调用。当第二个函数调用结束之后，执行过程会返回到第一个函数的正确位置。随后，第一个函数继续它的计算。

递归函数调用和非递归函数调用都采用上述这种机制。作为递归函数中函数调用机制的一个例子，下面全程跟踪函数调用super_write_vertical(–36)。首先，将number设置为–36，并调用super_write_vertical。实参–36被复制到形参number中，随后在number具有值–36时开始执行代码。在函数开始执行时，函数需要的所有重要信息存储到一个特殊的内存块中，该内存块称为函数的激活记录(activation record)。激活记录包含了关于函数在完成计算之后应该在什么地方返回的信息，它还包括函数的局部变量和参数的值。举例来说，如果super_write_vertical函数被一个主程序调用，那么激活记录就应该包括如下内容：

实际激活记录中的“返回位置”并不是真正指向主函数的代码行，但是当我们构想一个激活记录时，可以用这样的方式来考虑返回位置。

当激活记录就绪之后，函数开始执行。由于number是负数，因此if语句的布尔测试为true，从而输出负号。此时，计算过程即将进入递归调用，如下所示：

if (number < 0)

{

    cout << '-' << end;

    super_write_vertical(abs(number));

    //在super_write_vertical函数中进行一个递归调用。

    || This is Spot#1 referred to in the text。

}

这个函数使用它自己的number值(即36)和它自己的返回位置生成自己的激活记录。新的激活记录放在另一个激活记录的上面，如下图所示：

事实上，激活记录的集合存储在一个称为运行时栈(run-time stack)的堆栈数据结构中。每个函数调用都会把下一个激活记录压入运行时栈的顶部。

在本例中，第二次调用super_write_vertical时，它自己的number值等于36。接着，执行函数的代码，进入if-else控制结构的最后一个分支，然后又到达另一个递归调用，如下所示：

else

{

    super_write_vertical(number/10);

    //在super_write_vertical函数中，执行另一个递归调用。

    || This is Spot#2 referred to in the text.

    cout<< number % 10 << end;

}

为了执行这个递归调用，又要创建另一个激活记录(number现在被设置为3)，随后将激活记录压入运行时栈中：

super_write_vertical函数再一次开始执行。由于number被设置为3，因此函数进入处理只有一位数字的代码段。此时，程序输出数字3，并且在这个函数调用过程中不做其他的事情。

当第三个函数调用结束时，从堆栈中弹出它的激活记录。但是，就在弹出激活记录之前，激活记录提供一条最新的信息——告知从哪里继续进行计算。在本例中，从堆栈中弹出第三个激活记录，计算过程从图9-2中的Spot #2处继续进行。此时，还剩下两个激活记录，如下所示：

正如前文所述，计算现在位于图9-2中的Spot #2处，即下面代码的高亮部分：

else

{

    super_write_vertical(number/10);

    || This is Spot #2 referred to in the text.

    cout << number % 10 << end;

}

下一条语句是一条输出语句。它输出什么呢？从栈顶的激活记录可以看出，number是36，所以该语句输出6(即36%10)。然后，第二个函数调用结束，返回到图9-2中的Spot #1处。但是在Spot #1之后没有其他的工作要做，所以第一个函数也要返回。最初的函数调用的总体效果就是输出3个字符：一个负号，然后是3，最后是6。通常的函数调用机制的跟踪过程全部完成—— 不需要特别对待跟踪递归调用。在这个例子中，共有两级递归调用：

1. super_write_vertical(-36) 递归调用super_write_vertical(36)；

2. super_write_vertical(36) 递归调用super_write_vertical(3)。

通常，函数调用的深度要比这个例子深得多，但是即便是位于最深层，其函数调用机制也和这里跟踪的例子是相同的。

9.1.5  成功递归函数的一般形式

C++对在一个函数定义内如何使用递归调用没有任何限制。但是，为了使递归函数的定义确实可用，任何递归调用最终必须以一段不依赖于递归的代码结束——换句话说，也就是必须要有一个停止条件。函数可以调用它本身，递归调用又可以再调用该函数。这个过程可能会重复多次。然而，除非最后有一个递归调用本身不再产生递归调用，否则这个过程将不会停止。递归函数定义的通常原则如下：

通常，由一系列的if-else语句确定执行哪个分支条件。对于最初的函数调用，一种典型的情况是执行一个包含递归调用的分支条件。该递归调用又反过来执行一个包含另一个递归调用的分支条件。有时，每个递归调用会产生另一个递归调用，但是最终会进入一个停止条件。函数的每次调用最后必须进入一个停止条件，否则由于连续不断的递归调用，函数调用就永远也不会停止(实际上，无限递归调用并不会永远地运行下去，它将会非正常地终止，这是由于计算过程中过多激活记录的运行时栈将会耗尽有限的内存)。

9.1.6  自测习题

1. 在下面3个定义中，函数调用exercise(3)产生的输出是什么？

2. 激活记录包含哪些信息？

3. 使用哪种数据结构类型存储激活记录？为什么？

4. 如果一个递归函数没有基本条件，那么将会发生什么情况？

5. 当如下函数的实参为3时，其输出结果是什么？

void cheers(int n)

{

    if (n <= 1)

        cout<< "Hurrah" << endl;

    else

    {

        cout<< "Hip" << endl;

        cheers(n-1);

    }

}

6. 修改上一练习中的cheers函数，使函数首先输出“Hurrah”，然后输出n–1个“Hip”。再对其做进一步的修改，使“Hurrah”的前面和后面都输出n–1个“Hip”。再次修改该函数，使大约一半的“Hip”出现在“Hurrah”的前面，另一半的“Hip”出现在“Hurrah”的后面。

7. 编写一个以非负整数作为参数的递归函数。该函数在屏幕上输出由参数指定个数的星号‘*’，然后输出同样多的感叹号‘!’。要求不能使用循环或者局部变量。

8. 编写一个以字符串作为参数的递归函数，函数输出该字符串的反向字符。此函数的基本条件是空字符串。