Question

在理解了函数的嵌套调用之后，下面来认识一下函数的递归调用。不得不说，递归调用对于初学者来说，是个较为困难的知识点，想要搞懂它，并能掌握它的执行流程，需要有足够的耐性并保持一颗清醒的头脑。

1．递归调用与递归函数

递归调用的原理很简单，就是函数的自身调用。它其实就是一种特殊的函数嵌套调用。在上一节的例子中，我们在主函数中调用了函数 B，在函数 B 中又调用了函数 A。也就是嵌套调用的这几个函数是各不相同的。那我们可不可以嵌套调用同一个函数呢？可以的，C 语言允许函数调用自身，也就是在一个函数的函数体中，又调用了函数自己。例如：

首先定义一个函数 A，在它的函数体中又出现对函数 A 的调用，C 语言中就把这种调用函数自身的行为称为递归调用，而把拥有这种调用自身能力的函数称为递归函数。也就是说，函数 A 是一个递归函数，通过它的执行能引起函数的递归调用。

2．递归调用的终止

函数 A 被执行后，它的执行流程如图 4.6 所示。

图 4.6　函数 A 的递归调用

这个图中只显示了起始的执行流程片段，由于每次执行函数 A 时都会进行递归调用，所以它会无休止地进行下去，变成了无限递归，或称死递归。是不是想起了死循环？道理是差不多的。当这样的程序被执行后，程序会陷入死递归，容易造成系统瘫痪，最终导致程序栈空间被耗尽，引发程序出现崩溃现象。

为了防止死递归的发生，需要有效地控制递归调用，也就是在某种情况下能够让递归调用终止。怎么才能让递归调用终止呢？还得依靠我们的老朋友——return 语句。也就是在进行递归调用时，需要在满足某种条件的情况下，通过 return 语句来终止递归调用，即形成如图 4.7 所示的递归调用效果。

图 4.7　使用 return 语句终止递归调用

3．递归调用的算法原理

大家有没有考虑过，为什么要有递归调用？什么情况下才需要使用递归调用？这就需要了解递归调用的算法原理，也就是需要知道如何通过递归调用来达到所要求的功能。

递归调用的算法原理有点类似于我们所熟知的“愚公移山”，它的主体思想就是对于一个我们不容易完成的、比较大的目标，通过不断地对它进行分解化小，直到小到极致，也就是可以轻松完成的时候，再反过来一点点地由小到大，最终完成那个大的目标。

举个简单的例子，例如我们现在的大目标是“求 1～5 的累加和”，来看一下按照递归思想，如何对它逐步进行分解化小：

① 想要得到“1～5 的累加和”，现在只需得到“1～4 的累加和”，再与 5 相加；

② 想要得到“1～4 的累加和”，现在只需得到“1～3 的累加和”，再与 4 相加；

③ 想要得到“1～3 的累加和”，现在只需得到“1～2 的累加和”，再与 3 相加；

④ 想要得到“1～2 的累加和”，现在只需得到“1～1 的累加和”，再与 2 相加；

⑤“1～1 的累加和”是 1。

通过前 4 步的分解化小，在第 5 步得到了“1～1 的累加和”，它的结果为 1。由于这个结果是明确的，所以就不需要继续往下分解化小了。

接下来，以“1～1 的累加和”为 1 进行反推：

① 通过“1～1 的累加和”与 2 相加，得到“1～2 的累加和”为 3；

② 通过“1～2 的累加和”与 3 相加，得到“1～3 的累加和”为 6；

③ 通过“1～3 的累加和”与 4 相加，得到“1～4 的累加和”为 10；

④ 通过“1～4 的累加和”与 5 相加，得到“1～5 的累加和”为 15。

通过 4 步反推，最终得出了大目标“1～5 的累加和”为 15，如图 4.8 所示。

图 4.8　递归分解过程

4．编写递归函数

了解了递归的算法原理后，下面就来真正地实现这样功能的递归函数。

【 例 4-2 】编写一个递归函数，能够计算 1～n 的累加值，其中 n 的值大于等于 1，并在主函数中调用该函数。

我们将递归函数命名为“sum”，其形参定义为 int 类型，变量名为 n。返回值也是 int 类型。函数的具体代码如下：

在函数体中，首先使用 if 语句来判断形参变量 n 的值，若是等于 1，相当于求“1～1 的累加和”，对于这种情况，可确切地知道结果为 1，因此就通过第一个 return 语句终止递归调用，并将 1 作为结果返回。若形参变量的值并非是 1，则 if 语句中的表达式的值为假，第一个 return 语句就不会被执行，而第二个 return 语句会被执行。

第二个 return 语句被执行时，首先要计算表达式“sum(n – 1) + n”的值，表达式是一个加号运算符的算术表达式，而加号运算符的左操作数是一个递归调用。这个递归调用就相当于是一个分解化小的过程，它把原参数变量 n 的值减 1 之后作为新的参数进行递归调用。假设原形参变量 n 的值为 5，则递归调用时，新的函数参数值则为 4。所以表达式“sum(n – 1) + n”，就是把原来的求“1～5 的累加和”，分解化小为先求出“1～4 的累加和”，再将结果与 5 相加。

虽然递归调用是函数调用自身，但是在递归调用过程中，我们可以把它们理解为是不同的函数。也就是虽然它们有着相同的函数名，有着相同的函数体，但函数调用时的参数值是各不相同的。下面就以求“1～5 的累加和”为例，递归调用期间，各函数的参数和执行过程如图 4.9 所示。

图 4.9　递归调用时参数和执行过程

下面在主函数中来调用这个递归函数：

在主函数中，首先定义一个 int 类型变量 a，用于保存用户所输入的整数，然后使用 printf 函数提示用户输入一个大于 1 的整数，接着使用 scanf 函数获取用户的输入，最后通过 printf 函数打印输出 1 至用户指定整数的累加和。注意，我们直接将递归函数 sum 的调用语句作为 printf 函数的第 3 个参数（它对应着格式化字符串中的第 2 个点位符），这是没问题的，因为 sum 函数是一个有返回值类型的函数。

运行一下程序，结果如下：

Please enter an integer greater than 1:
5
The sum from 1 to 5 is 15.