C++ 递归(递归函数)

递归是一种编程技巧，函数使用修改后的参数反复调用自身，直到到达其起始条件(base case)，递归停止。

递归将问题分解为更小、更易于管理的子问题，从而为复杂问题提供更优雅、更完善的解决方案。

递归函数

递归函数是一种特别用于递归的函数，函数通过直接或间接调用自身来解决问题。它必须至少包含一个终止递归的基准条件和一个函数调用自身的递归条件。

• 基准条件 − 递归在达到特定条件后停止或结束的情况。
• 递归条件 − 函数反复调用自身，直到达到基准条件，并且值递减。

创建递归函数

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

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

   <function body>

   <return statement>
}

这里

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

调用递归函数

调用递归函数与调用任何其他函数类似，只需使用函数名并在 int 中提供必要的参数即可。 ma​​in() 函数体。

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

func_name(value);

递归示例

以下是 C++ 中递归函数的一个例子。这里，我们使用递归计算一个数的阶乘 -

#include <iostream>
using namespace std;

// 计算阶乘的递归函数
int factorial(int num) {
   // 起始条件
   if (num <= 1) {
      return 1;
   }
   // 递归情况
   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(4) 的形式将整数发送到名为"factorial"的函数。

首次调用: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);  // 尾递归调用
   }
}

头部递归

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

void printNumbers(int n) {
   if (n > 0) {
      printNumbers(n - 1);  // 首先递归调用
      cout << n << " ";     // 递归调用后的处理
   }
}

线性递归

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

int linearRecursion(int n) {
   if (n <= 0) {
      return 0;
   } else {
      return linearRecursion(n - 1) + 1;  // 线性递归调用
   }
}

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));  // 嵌套递归调用
   }
}

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

输出

91

递归的优势

• 简洁且减少样板代码 − 递归有助于简化具有内置递归结构的问题的求解，例如使用树或求解组合问题，使其更易于理解和实现。
• 回溯 − 递归非常适合回溯算法，该算法涉及检查所有可能的解决方案以找到满足特定条件的解决方案。
• 分治问题的有效解决方案 − 递归非常适合分治算法，在分治算法中，问题被分解为更小的子部分并逐一解决。这使得问题求解更加高效和容易。

递归 vs.迭代

递归是一种方法，其中函数使用修改后的参数反复调用自身，直到到达其基本情况(终止递归)。而迭代则涉及使用循环(例如 for、while 或 do-while)，其中涉及重复执行代码块，直到满足特定条件。

递归或迭代:何时使用?

递归

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

迭代

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

递归与迭代的比较

递归的局限性

以下是递归的局限性 -

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