C++ 递归（递归函数）

---

---

递归是一种编程技术，其中一个函数一遍又一遍地调用自身，并使用修改后的参数，直到它到达其基本情况，递归停止。

它将问题分解成更小、更容易管理的子问题，递归允许对复杂问题进行优雅和更好的解决方案。

递归函数

递归函数是一种特别用于递归的函数，其中一个函数直接或间接地调用自身以解决问题。它必须至少包含一个基本情况来终止递归和一个递归情况，其中函数调用自身。

• 基本情况 - 它是递归在达到特定条件后停止或结束的情况。
• 递归情况 - 它是函数一遍又一遍地调用自身并递减值的情况，直到它到达其基本情况。

创建递归函数

以下语法用于在 C++ 中实现递归函数：

function name(param_1, param_2..){
   <base condition>

   <function body>

   <return statement>
}

这里，

• 其中，function name(param_1, param_2..) 是一个声明为“name”的函数，根据需要传递多个参数。
• 现在函数体被分为三个子类别：基本条件、函数体和返回语句。
• 在基本条件中，我们将定义其基本情况，递归必须在其中停止或结束。
• 在函数体中，将定义一个递归情况，我们需要根据需要一遍又一遍地调用该函数。
• 最后，return 语句将返回函数的最终输出。

调用递归函数

调用递归函数就像调用任何其他函数一样，您将在 int main() 函数体中使用函数名并提供必要的参数。

要调用递归函数，请使用以下语法：

func_name(value);

递归示例

下面是 C++ 中递归函数的示例。在这里，我们使用递归计算数字的阶乘：

#include <iostream>
using namespace std;

// Recursive Function to Calculate Factorial
int factorial(int num) {
   // Base case
   if (num <= 1) {
      return 1;
   }
   // Recursive case
   else {
      return num * factorial(num - 1);
   }
}

int main() {
   int positive_number;
   cout << "Enter a positive integer: ";
   cin >> positive_number;
   if (positive_number < 0) {
      cout << "Wrong Input, Factorial is not Defined for Negative Integer" << endl;
   } else {
      cout << "Factorial of " << positive_number << " is " << factorial(positive_number) << endl;
   }
   return 0;
}

输出

Enter a positive integer: 4 (input)
Factorial of 4 is 24

解释

如果将输入 int positive_number 作为 4，它将整数发送到函数名“factorial”作为 factorial(4)

初始调用：factorial(4)

此函数将检查基本情况 (n<=1)，因为它不满足基本情况，因此继续执行递归情况并计算为“4 * factorial(3)”。

第二次调用：factorial(3)

此函数将再次检查基本情况，因为它不满足它，因此将再次继续执行递归情况，并计算为“3 * factorial(2)”。

第三次调用：factorial(2)

检查基本情况并计算“2 * factorial(1)”

第四次调用：factorial(1)

检查基本情况，现在由于函数满足小于或等于 1 的此基本情况条件，因此它将返回 1。

展开栈

现在，递归调用将开始返回：在第四次调用之后，它将再次从后面开始，首先返回到第三次调用。

返回到第三次调用：factorial(2)

我们已经有了 factorial(1) = 1，因此 factorial(2) 将返回“2 * factorial(1)”，即“2 * 1”，它返回为 factorial(2) 等于 2。

返回到第二次调用：factorial(3)

现在，factorial(2) 为 2，因此 factorial(3) 等于“3 * 2”，即 6。

返回到初始调用：factorial(4)

我们有 factoria(3) 返回 6，因此，factorial(4) 返回“4 * 6 = 24”。

递归类型

递归可以分为两种主要类型，每种类型都有自己的子类别：

1. 直接递归

当函数直接调用自身时发生直接递归：

简单直接递归

该函数使用问题的更简单或更小的实例调用自身。它用于解决诸如阶乘计算、斐波那契数列生成等问题。

尾递归

直接递归的一种形式，其中递归调用是函数中的最后一个操作。它用于解决累积计算和列表处理问题。

int factorial(int n, int result = 1) {
   if (n <= 1) {
      return result;
   } else {
      return factorial(n - 1, n * result);  // Tail recursive call
   }
}

头递归

在任何其他操作之前进行递归调用。处理在递归调用返回后发生。它用于树遍历和输出生成。

void printNumbers(int n) {
   if (n > 0) {
      printNumbers(n - 1);  // Recursive call first
      cout << n << " ";     // Processing after recursive call
   }
}

线性递归

每个函数调用都生成正好一个递归调用，形成一个线性的调用链。它用于简单的计数或求和。

int linearRecursion(int n) {
   if (n <= 0) {
      return 0;
   } else {
      return linearRecursion(n - 1) + 1;  // Linear recursive call
   }
}

2. 间接递归

当一个函数调用另一个函数时发生间接递归，这最终会导致原始函数被调用。这涉及两个或多个函数相互调用。

相互递归

在相互递归中，两个或多个函数以递归方式相互调用，形成循环依赖关系。它用于偶数和奇数分类以及语法分析。

#include <iostream>
using namespace std;

void even(int n);
void odd(int n);

void even(int n) {
   if (n == 0) {
      cout << "Even" << endl;
   } else {
      odd(n - 1);  // Calls odd
   }
}

void odd(int n) {
   if (n == 0) {
      cout << "Odd" << endl;
   } else {
      even(n - 1);  // Calls even
   }
}

int main() {
   even(4);  
   // Outputs: Even
   odd(5);   
   // Outputs: Odd
   return 0;
}

输出

Even
Even

嵌套递归

嵌套递归是一种间接递归的形式，其中一个递归函数在其自己的递归调用中进行另一个递归调用。它用于解决复杂的数学和算法问题。

#include <iostream>
using namespace std;

int nestedRecursion(int n) {
   if (n > 100) {
      return n - 10;
   } else {
      return nestedRecursion(nestedRecursion(n + 11));  // Nested recursive calls
   }
}

int main() {
   cout << nestedRecursion(95) << endl; // Outputs: 105
   return 0;
}

输出

91

递归的优点

• 简单性和减少样板代码 - 递归有助于简化解决具有内置递归结构的问题，例如处理树或通过使其更易于理解和实现来解决组合问题。
• 回溯 - 递归非常适合回溯算法，这些算法涉及检查所有可能的解决方案以找到满足某些条件的解决方案。
• 分治问题的有效解决方案 - 递归非常适合分治算法，其中问题被分解成更小的子部分并逐一解决。这使得解决问题更有效率和更容易。

递归与迭代

递归是一种函数一遍又一遍地调用自身并使用修改后的参数直到到达停止递归的基本情况的方法。而迭代涉及使用循环（例如 for、while 或 do-while），其中它涉及重复执行代码块，直到满足某个条件。

递归或迭代：何时使用？

递归

• 可以细分为类似子问题或具有自然递归模式（如树遍历或组合任务）且深度可控的问题。
• 当用户需要简单、更干净和可读的代码时，因为它提供了干净、正确排列的代码。
• 示例：树和图遍历、分治算法（如快速排序和归并排序），以及涉及回溯的问题（如解决迷宫或谜题）。

迭代

• 从内存和执行时间方面来看，迭代解决方案通常更有效，并且涉及简单的重复。
• 对于需要简单循环的问题，因为迭代通常更直接且更高效。
• 对于需要大量重复的问题，迭代更稳定，因为它不会冒堆栈溢出的风险。
• 示例：数组、向量和列表的循环，需要简单的数学计算和代码块的重复执行。

递归和迭代的比较

递归的局限性

以下是递归的局限性：

• 内存消耗 - 每次递归调用都会在调用栈中添加一个新的帧，这可能会消耗大量的内存。
• 堆栈溢出风险 - 由于递归依赖于调用栈来管理函数调用，因此深度递归会导致堆栈溢出，因为它超过了堆栈大小限制。
• 性能开销 - 递归函数可能不如迭代函数高效，因为它们涉及多个函数调用的开销和管理调用栈，这会严重影响性能，尤其是在深度递归的情况下。
• 调试复杂性 - 调试递归代码可能具有挑战性，尤其是在处理复杂递归或大型递归深度时。它需要仔细处理基本情况和逻辑。
• 空间复杂度 - 由于递归中的调用栈，它会导致消耗大量内存。