《C编程技巧：117个问题解决方案示例 》 —3.3　使用递归进行数字求和

3.3　使用递归进行数字求和

问题

你希望使用递归来进行数字求和。

解决方案

首先，你必须以递归形式表达此问题。如果符号表示求和，则表示递归形式中n个数的求和问题如下：

每次递归调用，计算n的问题都会简化到计算(n｜1)的问题。随着每次递归调用n的值减1，递归将以有限数量的步骤终止（递归调用）。

根据以下规格说明编写一个使用递归执行数字求和的C程序：

程序使用名为summation()的用户定义函数来执行数字求和。

函数summation()调用自身来执行求和。

代码

以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:\Code中，文件名为sum2.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理

在这个程序中，LOC 3～9包含main()函数的定义。LOC 10～16由summation()函数的定义组成。在LOC 6中，调用函数summation()，并将整数值4作为参数传递给该函数。这是函数summation()的第一次调用。参数的值（即4）被赋值给参数intM，它作为函数summation()内的局部变量。函数summation()由两个return语句组成：如果intM的值为1，则返回值1，否则，返回一个由函数调用组成的表达式（参见LOC 15）。因为intM的值是4，所以执行LOC 15，它想要返回以下值：

为了计算该表达式的值，计算机再次使用参数3调用函数summation()。这是对summation()的第二次调用。summation()中的局部变量在第一次执行时的值存储在堆栈中而不会被丢弃。在summation()的第二次执行期间，intM的值为3，因此，再次执行LOC 15，现在想要返回以下值：

3 + summation(2)                                                 表达式B

要计算此表达式的值，计算机再次使用参数2调用函数summation()。这是对summation()的第三次调用。summation()中的局部变量在第二次执行期间的值存储在堆栈中而不会被丢弃。在summation()的第三次执行期间，M的值为2，因此，再次执行LOC 15，现在想要返回以下值：

2 + summation(1)                                                表达式C

为了计算该表达式的值，计算机再次使用参数1调用函数summation()。这是对summation()的第四次调用。summation()中的局部变量在第三次执行期间的值存储在堆栈中而不会被丢弃。在summation()的第四次执行期间，intM的值为1，因此，此时执行LOC 13（而不是LOC 15）。LOC 13由return语句组成，执行此return语句并返回整数值1。随着return语句的执行，summation()的第四次执行也变得完整。

现在计算机控制被转移回summation()的第三次执行。回想一下，在计算表达式C时（即在summation()的第三次执行期间）对第四次执行summation()进行了调用。第四次执行summation()返回的值只是1，而这是summation(1)的值。在表达式C中插入此值，如下所示：

2 + summation (1) = 2 + 1 = 3

因此，表达式C的值为3，这是summation()的第三次执行。计算机执行return语句并返回值3以完成LOC 15的执行以及summation()的第三次执行。

现在计算机控制被转移回summation()的第二次执行。回想一下，在计算表达式B时（即在第二次执行summation()期间），调用了summation()的第三次执行。第三次执行summation()返回的值只是3，这是summation(2)的值。在表达式B中插入此值，如下所示：

3 + summation(2) = 3 + 3 = 6

因此，表达式B的值变为6，这是summation()的第二次执行。计算机执行return语句并返回值6，以便完成LOC 15的执行以及summation()的第二次执行。

现在计算机控制被转移回summation()的第一次执行。回想一下，在计算表达式A时（即在第一次执行summation()期间），调用了第二次执行summation()。第二次执行summation()返回的值只是6，而这是summation(3)的值。在表达式A中插入此值，如下所示：

4 + summation(3) = 4 + 6 = 10

因此，表达式A的值变为10，这是summation()的第一次执行。计算机执行return语句并返回值10以完成LOC 15的执行以及summation()的第一次执行。第一次执行summation()的调用是在LOC 6中完成的。第一次执行summation()返回的值（现在只有10）现在被赋值给intR（参见LOC 6）。这是整数1到4的求和的结果。在执行LOC 7之后，在屏幕上显示该结果。