C++递归/递归函数（详细讲解）

原理/理论

递归是编程中一种强大的技术，它允许函数自我调用。在C++中，递归通常用于解决某些类型的问题，如树形结构、分治算法等。下面我们将深入探讨C++中的递归知识，包括其原理、用法、作用等。

递归的原理

递归的核心思想是将问题分解为更小的子问题。这些子问题通常与原始问题相似，但规模更小。通过解决这些子问题，我们可以组合它们的解决方案来获得原始问题的解决方案。

递归的基本步骤如下：

1. 基线条件：这是递归终止的条件。当问题规模足够小时，基线条件将被满足，递归调用将停止。
2. 递归步骤：这是将问题分解为更小子问题的步骤。函数会自我调用，每个子问题的规模都比原始问题小。
3. 组合子问题的解决方案：当所有的子问题都被解决后，它们的解决方案被组合起来以形成原始问题的解决方案。

递归的作用

递归在编程中有很多用途，包括：

1. 解决问题：许多问题可以通过递归有效地解决，特别是那些可以自然分解为更小子问题的问题。例如，排序算法（如快速排序和归并排序）、搜索算法（如深度优先搜索和广度优先搜索）以及图算法（如Dijkstra算法和Prim算法）都可以用递归来实现。
2. 简化代码：对于某些问题，使用递归来编写代码可以使代码更简洁、更易于理解。由于每个递归调用都做类似的事情，这也有助于代码复用。
3. 抽象和分治策略：递归是一种强大的抽象工具，可以用来解决复杂的问题。通过将问题分解为更小的子问题，我们可以更容易地理解和解决原始问题。此外，分治策略（即将问题分解为独立的子问题，然后解决这些子问题并将结果组合起来）也是递归的核心概念。
4. 理解复杂概念：对于初学者来说，递归可能是一个难以理解的概念。然而，一旦掌握了它，就可以更好地理解许多复杂的编程概念，如动态规划、堆栈、队列等。
5. 处理无限数据结构：虽然在实际编程中很少遇到无限数据结构，但理论上，递归是处理这类数据结构的唯一方法。例如，无限斐波那契数列和无限链表只能通过递归来处理。

递归函数

递归函数是一种特殊的函数，它在其定义或实现中直接或间接地调用自身。递归函数通常用于解决一些可以通过分解为更小的子问题来解决的问题。在C++中，递归函数的定义和实现与其他函数类似，但是需要在函数的主体中调用自身。

递归函数的基本结构如下：

1. 基线条件：这是递归终止的条件。当问题规模足够小时，基线条件将被满足，递归调用将停止。
2. 递归步骤：这是将问题分解为更小子问题的步骤。函数会自我调用，每个子问题的规模都比原始问题小。
3. 组合子问题的解决方案：当所有的子问题都被解决后，它们的解决方案被组合起来以形成原始问题的解决方案。

生动的理解

递归，就是在运行的过程中调用自己本身

A. 构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单：
   这是递归的核心概念。一个函数要成为递归的，它必须在其定义中调用自身来处理比原始问题更小的子问题。这些子问题必须与原始问题相似，但规模更小。这样，通过解决这些子问题，我们可以组合它们的解决方案来得到原始问题的解决方案。
2. 不能无限制的调用本身，必须有个出口，化简为非递归状况处理：
   为了避免无限递归，递归函数必须有一个或多个基线条件。当满足基线条件时，递归调用停止。基线条件是递归终止的条件，通常当问题规模足够小时满足。这样，递归函数最终会化简为非递归状况处理，从而避免无限递归。

B. 递归可以解决的问题：

1. 阶乘：阶乘是一个典型的递归问题。例如，计算5的阶乘（5!）可以分解为计算4的阶乘（4!）和加上5。然后，4的阶乘可以分解为计算3的阶乘（3!）和加上4，依此类推，直到基线条件1! = 1。
2. 斐波那契数列：这是一个著名的递归问题。每个斐波那契数都是前两个数的和。例如，要计算第n个斐波那契数，可以递归地计算第n-1个和第n-2个斐波那契数，然后将它们相加。
3. 汉诺塔：这是一个经典的递归问题。汉诺塔问题要求将一堆盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且不能将一个较大的盘子放在较小的盘子上面。这个问题的解决方案是一个典型的递归过程，其中将问题分解为更小的子问题（移动较小的盘子）并将其解决，然后将结果组合起来（移动较大的盘子）以解决原始问题。
4. 杨辉三角的存取：杨辉三角是一个经典的数学问题，可以通过递归的方式求解。例如，可以使用递归来计算杨辉三角中的第n行数字。
5. 字符串回文判断：这是一个可以通过递归解决的问题。可以使用递归来比较字符串的首尾字符，然后递归地比较字符串的中间部分，直到字符串的长度为1或0。
6. 字符串全排列：全排列可以通过递归的方式求解。可以使用递归来生成所有可能的排列，直到所有字符都被排列。
7. 二分查找：二分查找是一个经典的递归算法。它通过将搜索空间一分为二来找到目标值。在每次递归调用中，算法将搜索空间缩小一半，直到找到目标值或搜索空间为空。
8. 树的深度求解：树的深度可以通过递归的方式求解。对于每个节点，算法将其子节点的最大深度作为该节点的深度。在每个递归调用中，算法处理一个子树并返回该子树的深度，直到达到叶节点或没有子节点为止。

C. 递归的过程：

递归过程通常包含以下几个步骤：

1. 定义：定义函数的基本结构并明确函数的名称和输入参数。
2. 基线条件：确定函数的基线条件。这是递归终止的条件，通常当问题规模足够小时满足。
3. 递归步骤：将问题分解为更小的子问题，并调用自身来处理这些子问题。这个步骤是递归的核心部分，它使函数能够自我调用以解决更小的子问题。
4. 组合子问题的解：当所有的子问题都被解决后，将这些子问题的解组合起来以形成原始问题的解。这个步骤是将递归转化为非递归的过程，通过组合子问题的解来获得原始问题的解。
5. 返回值：在函数体中返回结果或执行其他必要的操作以完成函数的执行。

通过以上步骤，递归函数实现了将复杂问题分解为更小的子问题并最终解决原始问题的目的。然而，使用递归时需要注意防止无限递归和栈溢出等问题，确保在基线条件下及时终止递归调用。

递归的过程可以理解为，把一个复杂的问题转化为一个个的小问题，而小问题能转化为更简单的问题，直到达到递归的“终点”——递归边界。递归边界是递归问题的特殊案例或者简单的情况，通过递归边界向上一层一层的返回数据，结束递归

示例例题

阶乘

#include <iostream>  
  
using namespace std;  
  
int factorial(int n) {  
    if (n == 0) {  // 基线条件  
        return 1;  
    } else {  // 递归步骤  
        return n * factorial(n - 1);  // 函数自我调用  
    }  
}  
  
int main() {  
    int number = 5;  
    cout << "Factorial of " << number << " = " << factorial(number) << endl;  
    return 0;  
}

在这个示例中，我们定义了一个名为factorial的函数，它接受一个整数参数n，并返回n的阶乘。如果n等于0，函数返回1，这是基线条件。否则，函数递归地调用自身，将n乘以n-1的阶乘。通过递归调用，我们可以将问题分解为更小的子问题，并最终解决原始问题。

在主函数中，我们定义了一个整数变量number，并将其设置为5。然后，我们调用factorial函数来计算5的阶乘，并将结果输出到控制台。

需要注意的是，递归函数必须有一个或多个基线条件来避免无限递归。在本例中，当n等于0时，函数返回1，这是基线条件。如果没有基线条件或基线条件设置不当，递归函数可能会导致栈溢出或无限循环等问题。

斐波那契数列

#include <iostream>  
  
using namespace std;  
  
int fibonacci(int n) {  
    if (n <= 1) {  // 基线条件  
        return n;  
    } else {  // 递归步骤  
        return fibonacci(n - 1) + fibonacci(n - 2);  // 函数自我调用  
    }  
}  
  
int main() {  
    int number = 10;  
    cout << "Fibonacci of " << number << " = " << fibonacci(number) << endl;  
    return 0;  
}

在这个示例中，我们定义了一个名为fibonacci的函数，它接受一个整数参数n，并返回第n个斐波那契数。如果n小于等于1，函数返回n，这是基线条件。否则，函数递归地调用自身，将第n-1个和第n-2个斐波那契数相加。通过递归调用，我们可以将问题分解为更小的子问题，并最终解决原始问题。

在主函数中，我们定义了一个整数变量number，并将其设置为10。然后，我们调用fibonacci函数来计算第10个斐波那契数，并将结果输出到控制台。

需要注意的是，递归函数必须有一个或多个基线条件来避免无限递归。在本例中，当n小于等于1时，函数返回n，这是基线条件。如果没有基线条件或基线条件设置不当，递归函数可能会导致栈溢出或无限循环等问题。

字符串回文判断

#include <iostream>  
#include <string>  
  
using namespace std;  
  
bool isPalindrome(string str, int start, int end) {  
    if (start >= end) {  // 基线条件  
        return true;  
    } else if (str[start] != str[end]) {  // 递归步骤  
        return false;  
    } else {  // 继续递归调用  
        return isPalindrome(str, start + 1, end - 1);  
    }  
}  
  
int main() {  
    string str = "abcdcba";  
    bool result = isPalindrome(str, 0, str.length() - 1);  
    cout << (result ? "Yes" : "No") << " " << str << " is a palindrome." << endl;  
    return 0;  
}

在这个示例中，我们定义了一个名为isPalindrome的函数，它接受一个字符串str、起始索引start和结束索引end作为参数，并返回一个布尔值表示该字符串是否为回文。如果start大于或等于end，说明已经比较完了整个字符串，返回true，这是基线条件。否则，我们比较str[start]和str[end]是否相等，如果不相等，说明该字符串不是回文，返回false。如果相等，则递归地调用isPalindrome函数，传入更新后的起始索引和结束索引（即start + 1和end - 1）。通过递归调用，我们可以将问题分解为更小的子问题，并最终解决原始问题。

在主函数中，我们定义了一个字符串变量str，并将其设置为"abcdcba"。然后，我们调用isPalindrome函数来检查该字符串是否为回文，并将结果存储在布尔变量result中。最后，我们输出结果。如果结果为真，则输出"Yes"，否则输出"No"。

最后

在解决递归问题时，确实关注整体结构和递归边界，而不是过分纠结于细节。递归是一种将问题分解为更小子问题的策略，理解递归问题的整体结构和递归边界是关键。

递归边界是确定递归何时结束的条件，正确地确定递归边界是确保递归算法正确运行的关键。一旦确定了递归边界，就可以根据问题的具体情况设计递归函数，将问题分解为更小的子问题，并逐个解决这些子问题。

在设计和实现递归函数时，要确保递归调用能够正确地解决子问题，并将子问题的解组合起来以形成原问题的解。通常，递归函数会包含一个或多个递归调用，以便处理更小的子问题。

因此，在解决递归问题时，整体把握和关注主要结构是重要的。不过，理解递归的内部运作机制对于深入理解递归和解决复杂问题也是有帮助的。但对于初学者或解决常见递归问题，关注整体结构和递归边界通常是足够有效的策略。