编程技能：递归

专栏导航

上一篇：Windows 编程辅助技能：格式工厂的使用

回到目录

下一篇：计算机基础：内存模型

本节前言

递归，其实在基础 C/C++ 课程中，我们就学习过。我相信，大多数的学生，应该是知道递归这个东西。

不过呢，在这里，我还是要来领着大家复习一下递归。

递归的英文是 recursive 。

在学习递归的时候，重点在于，了解递归的执行过程。

递归算法，说起来，其实是一种比较复杂的算法。

也许，在基础的 C/C++ 学习中，教材上的案例，你用大脑来进行心算，就可以了解递归的执行思路。

然而，我们也可以使用心算的方法，而是使用试数的办法，来了解递归的执行过程。

一.    本节代码

#include <stdio.h>int calcu(int num);int main()
{int num, res;num = 6;res = calcu(num);if (-1 == res){printf("提供的数太小了，请修改为大于或等于 1 的整数。\n");}else{ printf("计算结果为：%d\n", res);}return 0;
}int calcu(int num)
{int res_val;if (num < 1){return -1;}else if (1 == num){return 1;}else{ res_val = 3 * calcu(num - 1) - 1;return res_val;}
}

代码还是不难的。

接下来，请你自己将以上的代码添加到 Visual Studio 的解决方案里面。

关于使用 Visual Studio 来建立解决方案，添加源代码，编译运行的知识，你可以参考下面的两个链接。

参考课节：使用 VS2010 编写 C语言程序

参考课节：用 VS2019 编写C语言程序

推荐你使用 VS2019 来编写程序。因为 VS2019 版本更高，提供的功能更多。

当你使用 Visual Studio，将本分节的代码输入到解决方案里面，并且完成了编译运行的步骤以后，我们继续往下看。

二.    试数

对于一个比较简单的程序，我们通常不需要试数。而对于复杂一些的程序，我们往往会需要通过试数，来了解一个程序的运行过程。

本分节，我们就对第一分节中的程序，进行试数，以观察本程序的运行过程。

在开始试数之前，我们先来简单地来说一说程序的基本含义。

（一）程序的基本含义

首先呢，我们来看 main 函数。

本部分代码如下所示。

1~3 行是头文件包含与函数声明。函数声明语句中，声明了 main 函数下方的 calcu 函数。

calcu 函数，它是本节文章的递归算法主体函数。

5~22 行，是 main 函数。

程序开头声明了两个 int 型变量，一个是 num，一个是 res 。

res，就是 result 的意思，一般用它保存计算结果，或者作为返回值。在本节中，用 res 变量来接收递归函数 calcu 的最终计算结果。

num，它是刚开始调用递归函数的时候，传递的参数。

第 8 行，将 num 赋值为 6 。

第 10 行，调用 calcu 函数，参数为 num，也就是 6 。返回值由 res 来接收。

代码第 12 行到第 19 行，根据 res 的不同值，输出不同的信息。

如果 res 的值为 -1，则给出错误提示与建议信息。

如果 res 的值不为 -1，则将 res 的值输出。

最后，在第 21 行，main 函数返回 0 值。

到了这里，main 函数的部分，我们就算是讲完了。

接下来，我们来看一看 calcu 函数。代码如下。

第 24 到第 40 行，为 calcu 函数。

函数的开头声明了 res_val 函数。

接下来，根据参数 num 的不同值，分别进行不同的处理。

如果 res 为小于 1 的整数，则返回 -1 。

如果 res 等于 1，则返回 1 。

如果 res 为 大于 1 的整数，则计算表达式【3 *calcu(num - 1) - 1】，并将表达式的值赋给 res_val 。在这里，我们本身处于 calcu 函数，而此处又调用了 calcu 函数。函数自己调用自己，这就是递归。所谓的递归，正是体现在【res > 1】的情况的处理代码之中。

在这里，对于【res > 1】的情况的处理，对于此种情况的执行流程，是递归的真正含义所在。在试数的时候，我会细讲这一块。

另外呢，在【 res 等于 1】这一情形里，我没有将其写作【 res == 1】，而是写作【1 == res】，这是为了防止出错。在马虎之下，我们可能将【res == 1】写作【res = 1】。真的出现了这种错误，那么，程序不会报错，因为语法是对的。然而，它却出现了逻辑错误，而导致执行之中出现了问题。

也许，大家在学习此处代码的时候，自己也能够知道，不应该将【res == 1】写为【res = 1】，然而，当你面对着几万行，几十万行的代码，在烈日炎炎的大夏天，吹着空调都还觉得热的时候，心烦烦躁不堪，难免会出现一些个马虎的情形。也许，你的马虎，就是将【res == 1】写为了【res = 1】。

为了减少和避免这样的小问题，基础教材里面，都是推荐，将常数写在左边，将变量写在右边。也就是，写作【1 == res】，而不是写作【res == 1】。

写作【1 == res】的话，即使你不慎将其错误地写成了【1 = res】，那么，编译器也会立即报错，因为这确实是一个语法错误。所以呢，写成【1 == res】，还是比较保险一些的。

（二）试数过程

既然是讲完了函数的基本含义，那么，接下来，我们就正式地来开展着试数。

函数的执行，会从 main 函数开始。

然后呢，执行【num = 6】这一行，将 num 赋值为 6 。

接下来，执行到【res = calcu(num)】这一行。此行为第 10 行代码。

当执行到第 10 行代码的时候，程序不能够立即计算出结果。因为，需要先执行完 calcu 函数，获得 calcu 函数的返回值，才能够得到计算结果。

所以，到了这里，我们得先前往 calcu 函数，去执行函数代码 。

第 1 次执行 calcu 函数：

由于是第一次执行 calcu 函数，且我们知道，我们可能会在递归过程中，多次调用 calcu 函数，所以呢，我们暂且给本次的 calcu 函数一个新的记法，叫做 calcu<1> 。

第一次执行 calcu 函数的时候，传入的参数，是主函数中传第的 num 变量的值，6 。所以呢，在calcu<1> 里面，形参变量 num 的值为 6 。

【num < 1】条件不符合，【1 == num】条件仍然不符合，因此执行 else 部分的代码。

else 部分执行如下两行代码。

对于图3 中的红色框线所示的代码，首先要去执行的是【res_val = 3 * calcu(num - 1) - 1;】。如果，赋值号右边全是常数或者普通变量，则这一行代码可以直接计算出来。可是，这一行代码却包含着函数调用代码【calcu(num - 1)】。为了获得整个的表达式的计算结果，程序需要首先计算确定【calcu(num - 1)】返回值。

因此，当碰到了包含有函数调用代码【calcu(num - 1)】的时候，我们又得进入 calcu 函数了。执行函数调用【calcu(num - 1)】之前，由于此时的 num 为 6，所以，【num - 1】为 5 。所以，此次要去执行的【calcu(num - 1)】调用，实际上要去执行的，是【calcu(5)】。

好了，我们去新的 calcu 函数里看一看。

第 2 次执行 calcu 函数：calcu<2>

本次进入 calcu 函数的时候，形参 num 为 5 。

在对 num 进行判断的时候，依然是说，【num < 1】和【1 == num】均不符合，因此，依然是执行 else 部分的代码。也就是，要去执行下图所示的代码。

其中又是包含着函数调用代码【calcu(num - 1)】，还是不能立即得到表达式【3 * calcu(num - 1) - 1】的值。为了得到整个表达式的值，首先需要计算确定【calcu(num - 1)】的返回值。

为此呢，我们又得是执行函数调用代码【calcu(num - 1)】了。此刻，形参 num 的值为 5 。因此，【num - 1】为 4 。所以呢，此次要去执行的【calcu(num - 1)】调用，实际上要去执行的，是【calcu(4)】。

第 3 次执行 calcu 函数：calcu<3>

本次进入 calcu 函数的时候，形参 num 为 4 。

在对 num 进行判断的时候，依然是说，【num < 1】和【1 == num】均不符合，因此，依然是执行 else 部分的代码。也就是，要去执行下图所示的代码。

其中又是包含着函数调用代码【calcu(num - 1)】，还是不能立即得到表达式【3 * calcu(num - 1) - 1】的值。为了得到整个表达式的值，首先需要计算确定【calcu(num - 1)】的返回值。

为此呢，我们又得是执行函数调用代码【calcu(num - 1)】了。此刻，形参 num 的值为 4 。因此，【num - 1】为 3 。所以呢，此次要去执行的【calcu(num - 1)】调用，实际上要去执行的，是【calcu(3)】。

第 4 次执行 calcu 函数：calcu<4>

本次进入 calcu 函数的时候，形参 num 为 3 。

在对 num 进行判断的时候，依然是说，【num < 1】和【1 == num】均不符合，因此，依然是执行 else 部分的代码。也就是，要去执行下图所示的代码。

其中又是包含着函数调用代码【calcu(num - 1)】，还是不能立即得到表达式【3 * calcu(num - 1) - 1】的值。为了得到整个表达式的值，首先需要计算确定【calcu(num - 1)】的返回值。

为此呢，我们又得是执行函数调用代码【calcu(num - 1)】了。此刻，形参 num 的值为 3 。因此，【num - 1】为 2 。所以呢，此次要去执行的【calcu(num - 1)】调用，实际上要去执行的，是【calcu(2)】。

第 5 次执行 calcu 函数：calcu<5>

本次进入 calcu 函数的时候，形参 num 为 2 。

在对 num 进行判断的时候，依然是说，【num < 1】和【1 == num】均不符合，因此，依然是执行 else 部分的代码。也就是，要去执行下图所示的代码。

其中又是包含着函数调用代码【calcu(num - 1)】，还是不能立即得到表达式【3 * calcu(num - 1) - 1】的值。为了得到整个表达式的值，首先需要计算确定【calcu(num - 1)】的返回值。

为此呢，我们又得是执行函数调用代码【calcu(num - 1)】了。此刻，形参 num 的值为 2 。因此，【num - 1】为 1 。所以呢，此次要去执行的【calcu(num - 1)】调用，实际上要去执行的，是【calcu(1)】。

第 6 次执行 calcu 函数：calcu<6>

本次进入 calcu 函数的时候，形参 num 为 1 。

在对 num 进行判断的时候，【num < 1】不符合条件，但是【1 == num】是符合的。

所以呢，本次执行下述代码。

看到了吧，将整数 1 作为返回值，予以返回。

调用当前的 calcu 函数的，也就是调用 calcu<6> 的，是 calcu<5> 。所以呢，接下来，我们回到 calcu<5> 里面。

返回 calcu<5> ：

当初，我们是在下述代码中暂停的。

对于图3，我们当初是因为在代码行【res_val = 3 * calcu(num - 1) - 1;】之中遇到了【calcu(num - 1)】，因为当时不能够确定【calcu(num - 1)】的返回值，所以才去进行函数调用的。此时，我们已经得知了【calcu(num - 1)】的返回值，它等于 1 。所以呢，此时，我们可以将【calcu(num - 1)】看作是返回值 1 。因此，图 3 中的代码，相当于下面的截图所示的代码。

经计算，res_val 结果为 2，然后通过【return res_val;】语句，将 2 作为返回值，予以返回。

此时，我们处在 calcu<5> 之中，当初调用 calcu<5> 的，是 calcu<4> 。我们回到 calcu<4> 看一看。

返回 calcu<4> ：

当初，我们是在下述代码中暂停的。

对于图3，我们当初是因为在代码行【res_val = 3 * calcu(num - 1) - 1;】之中遇到了【calcu(num - 1)】，因为当时不能够确定【calcu(num - 1)】的返回值，所以才去进行函数调用的。此时，我们已经得知了【calcu(num - 1)】的返回值，它等于 2 。所以呢，此时，我们可以将【calcu(num - 1)】看作是返回值 2 。因此，图 3 中的代码，相当于下面的截图所示的代码。

经计算，res_val 结果为 5，然后通过【return res_val;】语句，将 5 作为返回值，予以返回。

此时，我们处在 calcu<4> 之中，当初调用 calcu<4> 的，是 calcu<3> 。我们回到 calcu<3> 看一看。

返回 calcu<3> ：

当初，我们是在下述代码中暂停的。

对于图3，我们当初是因为在代码行【res_val = 3 * calcu(num - 1) - 1;】之中遇到了【calcu(num - 1)】，因为当时不能够确定【calcu(num - 1)】的返回值，所以才去进行函数调用的。此时，我们已经得知了【calcu(num - 1)】的返回值，它等于 5 。所以呢，此时，我们可以将【calcu(num - 1)】看作是返回值 5 。因此，图 3 中的代码，相当于下面的截图所示的代码。

经计算，res_val 结果为 14，然后通过【return res_val;】语句，将 14 作为返回值，予以返回。

此时，我们处在 calcu<3> 之中，当初调用 calcu<3> 的，是 calcu<2> 。我们回到 calcu<2> 看一看。

返回 calcu<2> ：

当初，我们是在下述代码中暂停的。

对于图3，我们当初是因为在代码行【res_val = 3 * calcu(num - 1) - 1;】之中遇到了【calcu(num - 1)】，因为当时不能够确定【calcu(num - 1)】的返回值，所以才去进行函数调用的。此时，我们已经得知了【calcu(num - 1)】的返回值，它等于 14 。所以呢，此时，我们可以将【calcu(num - 1)】看作是返回值 14 。因此，图 3 中的代码，相当于下面的截图所示的代码。

经计算，res_val 结果为 41，然后通过【return res_val;】语句，将 41 作为返回值，予以返回。

此时，我们处在 calcu<2> 之中，当初调用 calcu<2> 的，是 calcu<1> 。我们回到 calcu<1> 看一看。

返回 calcu<1> ：

当初，我们是在下述代码中暂停的。

对于图3，我们当初是因为在代码行【res_val = 3 * calcu(num - 1) - 1;】之中遇到了【calcu(num - 1)】，因为当时不能够确定【calcu(num - 1)】的返回值，所以才去进行函数调用的。此时，我们已经得知了【calcu(num - 1)】的返回值，它等于 41 。所以呢，此时，我们可以将【calcu(num - 1)】看作是返回值 41 。因此，图 3 中的代码，相当于下面的截图所示的代码。

经计算，res_val 结果为 122，然后通过【return res_val;】语句，将 122 作为返回值，予以返回。

此时，我们处在 calcu<1> 之中，当初调用 calcu<1> 的，是 main 函数 。我们回到 main 函数看一看。

返回 main 函数：

当时我们是在下述代码中的狂色框线位置暂停的。

由于红色框线中包含着函数调用语句【calcu(num)】，由于当时不能够确定【calcu(num)】的值，因此，我们需要通过执行函数调用，计算得到【calcu(num)】的返回值，才能够继续执行下去。此时，我们已经是能够知道【calcu(num)】的返回值了，它等于 122 。

将图 10 中的【calcu(num)】替换为 122，继续执行代码，则 res 被赋值为 122 。

继续往下执行，由于 res 不为 -1，因此，执行 else 部分的代码。

在 else 部分里面，将 res 变量的值予以输出。

执行完了 else 部分的代码以后，再执行最终的【return 0】语句。

至此，本程序执行完毕，我们的试数工作结束。

程序的执行结果如下。

总结

关于试数，我这里的写作步骤，还是显得有些麻烦。如果是你自己在自己的草稿纸或者在 word 文档，或者是在记事本里面进行着演算的时候，其实你也可以根据自己对程序代码的掌握情况，简化其中的某些个步骤。

试数过程，是我们学习数据结构与算法，学习递归，学习一些个有难度的代码的时候，可以采用的一种辅助做法。

本节，我们讲解递归，主要地，还是为了让大家了解试数的写法。

在我这里，暂时地，我就演示到这里。

无论在本专栏里面，是否涉及对某些个代码段的试数，你都可以自己去作试数工作，跟踪观察代码的运行状况。

结束语

本节内容，我在写作之前，还是有一些个畏难情绪的。

实际去写的时候，也就是那么回事吧。麻烦，不过，该去写的，还得是硬着头皮去写。

不写，也没人替我写啊。

希望我所写的内容，你已经理解了。

本节结束。

 专栏导航

上一篇：Windows 编程辅助技能：格式工厂的使用

回到目录

下一篇：计算机基础：内存模型