|
5.1.5 函数的递归调用
在函数调用中，通常我们都是在一个函数中调用另外一个函数，以此来完成其中的某部分功能。例如，我们在main()主函数中调用PowerSum()函数来计算两个数的平方和，而在PowerSum()函数中，又调用Power()函数和Add()函数来计算每个数的平方并将两个平方加和起来成为最终的结果。除此之外，在C++中还存在另外一种特殊的函数调用方式，那就是在一个函数内部调用它自己本身，这种方式也被称为函数的递归调用。
函数的递归调用，实际上是实现函数的一种特殊方式。当递归函数被调用的时候，会产生一个自己调用自己的循环，这个循环会不断地递归进行下去，直到最后一次函数调用在特殊条件下，也就是满足了递归的终止条件，不再继续调用自身而是返回某个具体的结果数据。这时，所有调用这个函数的上层函数会依次返回，直到我们最初对这个函数的调用返回，获得其结果数据。虽然函数的递归调用每次调用的都是自己，但是每次递归调用的条件，也即是函数参数，往往有所不同。正是调用条件的变化，才有可能使函数满足终止条件并返回一个具体的结果数据，不再继续递归地调用自身，这也即是递归调用的终点。
函数的递归调用虽然形式上比较复杂，但是它在处理那些可以把一个大问题分解成一个已知的结果与另一个类似的小问题，需要重复多次做相似的事情才能最终解决的问题时，因为函数的递归调用本身所表达的意义就是循环往复地做同一件事情，所以在处理这类问题上有着天然的优势。例如，我们要统计某个字符在目标字符串中出现的次数。通常，我们的思路是用for循环遍历整个字符数组，然后逐个字符地进行匹配统计。而如果采用递归函数的思路来解决这个问题，那么整个统计过程就变为：从目标字符串的开始位置查找这个字符，如果找到，那么字符出现的次数就成了已经找到的这一次加上在剩下的字符串中出现的次数，在程序中我们可以用“1 + CountChar(pos+1, c)”来表示，其中“1”表示已经找到的字符出现一次，而“CountChar(pos+1, c)”则代表了字符在剩下的字符串中出现的次数，加起来刚好就是字符在整个字符串中出现的次数。这里的“CountChar(pos+1, c)”就是在变更开始条件后对CountChar()函数的递归调用，进行第二次查找与统计。第二次查找也会进行类似的查找统计过程，如果找到则会第三次调用CountChar()函数继续向后继续查找统计。这个过程会不断地持续进行下去，直到最后满足递归的终止条件——查找到了字符串的结尾，再也找不到这个字符——为止。在这个过程中，有需要循环往复执行的相同动作——从字符串开始位置查找目标字符；有不同的开始条件——在字符串的不同位置开始查找；有终止条件——在字符串中再也找不到目标字符。有了这三个特征，我们就可以用函数的递归调用更轻松而自然地解决这个问题：
// countchar.cpp 统计一个字符串中某个字符出现的次数
#include
#include // 引入字符查找函数strchr()所在的头文件
using namespace std;
// 用函数的递归调用实现统计字符在字符串中出现的次数
int CountChar(const char* str,const char c)
{
// 从字符串str的开始位置查找字符c
char* pos = strchr(str,c);
// 如果strchr()函数的返回值为nullptr，则意味着
// 在字符串中再也找不到目标字符，递归的终止条件得到满足
// 则结束函数的递归调用，直接返回本次的查找结果0
if(nullptr == pos)
{
return 0;
}
// 如果没有达到终止条件，则将本次查找结果1统计在内，
// 并在新的开始位置pos + 1开始下一次查找，实现函数的递归调用
return 1 + CountChar(pos + 1,c);
}
int main()
{
// 字符串
char str[] = "Thought is a seed";
char c = 'h'; // 目标字符
// 调用CountChar()函数进行统计
int nCount = CountChar(str,c);
// 输出结果
cout |