C++递归函数的用法（函数的递归调用，非常详细）

C++ 在函数调用的过程中，允许在一个函数内部调用另一个函数，以实现某部分功能。

例如，在 main() 函数中，我们可能会调用 PowerSum() 来计算两个数的平方和。PowerSum() 可能会进一步调用 Power() 和 Add() 函数来分别计算平方和加法，从而得到最终结果。

在 C++ 中，除在不同函数间进行调用外，还存在一种特殊的调用方式，称为递归调用。

递归调用发生在一个函数在其内部调用自己，这种调用形式创建了一个自我循环，直到满足特定的终止条件，具备这样特征的函数又称为递归函数。当递归调用的终止条件被满足时，函数将停止调用自己并逐层返回，直到最初的调用完成。

递归调用虽然在形式上较为复杂，但它在解决可分解为相似子问题的问题时具有天然优势。这些问题通常涉及重复执行相似操作，直到达到已知结果。

例如，统计字符串中某个字符出现次数的任务。传统方法可能使用 for 循环遍历字符串同时比对字符。而递归方法则将问题分解为：

在字符串的当前位置查找字符，如果找到，最终结果次数即为“当前找到的次数加上在剩余字符串中找到的次数”，可以用表达式“1 + CountChar(pos+1, c)”表示，其中“1”代表当前位置字符出现的次数，“CountChar(pos+1, c)”代表在剩余字符串中字符出现的次数。每次递归调用都会更新开始条件并继续搜索，直至满足终止条件—到达字符串末尾。

递归调用的关键在于三个要素：重复执行相同操作、变化的开始条件以及明确的终止条件。当具备这三种情况时，递归法提供了一种优雅且直观的解决方案。

// 统计一个字符串中某个字符出现的次数
#include <iostream>
#include <cstring> // 包含字符查找函数strchr()所在的头文件
using namespace std;

// 用函数的递归调用实现统计字符在字符串中出现的次数
int CountChar(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 << "字符'" << c << "'在'" << str << "'中出现了"
         << nCount << "次" << endl;

    return 0;
}

在执行过程中，当 CountChar() 函数在主函数中第一次被调用时，第一个参数 str 指向的字符串是"Thought is a seed"。进入 CountChar() 函数后，strchr() 函数会在字符串中找到字符 'h' 出现的位置，并将它保存到字符指针 pos 中。此时，尚不满足终止条件（nullprt == pos），因此执行return 1 + CountChar(pos+1,c)，将本次查找结果统计在内，并将递归的开始条件变更为 pos+1。这样，第二次递归调用 CountChar() 函数时，参数 str 指向的字符串变为"ought is a seed"。

在第二次进入 CountChar() 函数执行时，strchr() 函数会找到字符 'h' 第二次出现的位置。由于递归的终止条件依然未满足，函数继续将本次查找的结果统计在内并修改开始条件，并将 CountChar() 函数的 str 参数指向 "t is a seed"，然后开始第三次递归调用。

在第三次进入 CountChar() 函数执行时，strchr() 函数在剩下的字符串中再也找不到目标字符，递归的终止条件得到满足，函数直接返回本次的查找统计结果 0（return 0;），不再继续递归调用 CountChar() 函数。然后逐层向上返回，最终结束整个函数递归调用的过程，得到最终结果 2，也就是目标字符在字符串中出现的次数。

整个过程如下图所示：


函数的递归调用本质上是将一个大问题不断地分解成多个相似的小问题，通过不断细分，直到小问题被解决，最终解决最初的大问题。

例如，在这个例子中，最初的大问题是统计字符串中的目标字符的个数。这个大问题被分解为当前已找到的目标字符数 1 和剩余字符串中目标字符的个数 CountChar(pos+1，c)。计算剩余字符串中的目标字符数时，又可以采用同样的策略进一步细分，直至剩余字符串中没有目标字符，无法继续细分为止。

从这里可以看出，函数的递归调用实际上是一个循环过程。我们必须确保函数能够达到递归的终止条件，以结束递归。

例如，在这里我们不断地调整查找的开始位置，直到最后无法再查找到目标字符（因而满足终止条件）。否则，函数将无限地递归调用下去，最终形成一个无限循环，永远无法得到结果。这是我们在设计递归函数时需要特别注意的。

函数的递归调用通过在一个函数中循环调用自身来实现。从本质上讲，函数的递归调用是一种特殊形式的循环。因此，我们也可以将递归调用改用循环结构来实现。

例如，上面的 CountChar() 函数可以用循环结构改写为：

// 用循环结构来实现在字符串中统计指定字符出现的次数
int CountChar(const char* str, const char c)
{
    int nTotal = 0;  // 记录字符出现的次数
    // 在字符串中查找字符，并对结果进行判断
    // 如果 strchr() 返回 nullptr，则表示查找完毕，循环结束
    while(nullptr != (str = strchr(str, c)))
    {
        ++nTotal;    // 将找到的字符统计在内
        ++str;       // 字符串往后移动，开始下一次循环
    }
    return nTotal;
}

递归调用虽然在某些情况下可以用循环结构来实现，或者是出于性能上的考虑，但我们仍有充分的理由选择递归来解决问题。总之，递归调用在处理某些难以用循环结构解决的问题时显得尤为有效。

例如，当要从数组中找出连续子数组的最大和值时，使用循环结构来解决这个问题可能会非常复杂且性能低下。相反，递归允许我们将问题分解为更小、更易于管理的子问题。我们可以将数组分为左右两部分，并递归地寻找最大和值的子数组，无论是在左侧、右侧还是跨越中点的子数组。

递归调用的优势在于它能够将复杂问题分解为相似的子问题，直至达到可以直接解决的规模。这种方法不仅更符合人类的思维方式，而且在很多情况下，递归的性能也会优于循环结构。

此外，递归调用还有助于简化代码逻辑，提高代码的可读性和可维护性。在实际应用中，递归通常是解决分治算法问题的首选方法，如归并排序、快速排序和树的遍历等。