C++ 递归

一、递归编程技术简介

递归是一种编程技术，其中函数不断地调用自身，带有修改后的参数，直到达到基本情况，此时递归停止。

递归能够将问题分解为更小、更易于管理的子问题，从而允许以优雅的方式解决复杂的问题。

递归函数

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

基本情况

这是递归停止或结束的情况。

递归情况

这是函数不断重复调用自身的情况，直到达到基本情况。

创建递归函数

以下是在 C++ 中实现递归函数的语法：

function name(param_1, param_2..){
   <基本条件>

   <函数体>

   <返回语句>
}

这里，

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

调用递归函数

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

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

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 << "输入一个正整数: ";
   cin >> positive_number;
   if (positive_number < 0) {
      cout << "错误输入，负整数没有阶乘定义" << endl;
   } else {
      cout << "数 " << positive_number << " 的阶乘是 " << factorial(positive_number) << endl;
   }
   return 0;
}

输出

输入一个正整数: 4 (输入)
数 4 的阶乘是 24

解释

如果输入的 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) 我们已经有 factorial(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 << "偶数" << endl;
   } else {
      odd(n - 1);  // 调用 odd
   }
}

void odd(int n) {
   if (n == 0) {
      cout << "奇数" << endl;
   } else {
      even(n - 1);  // 调用 even
   }
}

int main() {
   even(4);  
   // 输出: 偶数
   odd(5);   
   // 输出: 奇数
   return 0;
}

输出

偶数
偶数

嵌套递归

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

#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; // 输出: 91
   return 0;
}

输出

二、递归的优点

简洁性和减少样板代码

递归有助于简化那些具有内置递归结构的问题的解决方法，例如处理树结构或者通过更容易理解与实现的方式来解决组合问题。

回溯

对于涉及检查所有可能解决方案以找到符合特定标准的解的回溯算法来说，递归是一个很好的选择。

分治法的有效解决方案

递归非常适合分治算法，在这种算法中，问题被分解成更小的部分并逐一解决。这使得问题解决更加高效且容易。

三、递归与迭代

递归

递归是一种方法，其中一个函数通过带有修改后的参数反复调用自身，直到达到基本情况来停止递归。而迭代则是指使用循环（如 for、while 或 do-while），反复执行代码块直到某个条件被满足。

使用递归还是迭代？

递归

适用于可以被分解为相似子问题的任务，或者是具有自然递归模式的任务，例如树的遍历或组合任务，并且递归深度可管理。当用户需要简洁、清晰且易读的代码时，因为它提供了干净整洁的代码。示例：树和图的遍历，分治算法（如快速排序和归并排序），以及涉及回溯的问题（如解决迷宫或谜题）。

迭代

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

四、递归与迭代的比较

特点	递归	迭代
时间复杂度	可能更高，因为其反复调用函数的特性。	相对较低。
空间复杂度	由于调用堆栈，递归通常使用更多内存。	使用固定数量的内存。
代码大小	在递归中，代码大小较小。	相对较大的代码大小。
执行速度	当使用递归时，执行速度较慢。	执行速度更快。

五、递归的局限性

内存消耗

每一次递归调用都会向调用堆栈添加一个新的帧，这可能会消耗大量的内存。

堆栈溢出风险

由于递归依赖于调用堆栈来管理函数调用，深度递归可能导致堆栈溢出，因为它超过了堆栈大小的限制。

性能开销

递归函数可能比迭代版本效率更低，因为它们涉及到多次函数调用和管理调用堆栈的开销，这对性能的影响尤其明显，特别是在深度递归情况下。

调试复杂度

调试递归代码可能是具有挑战性的，特别是在处理复杂的递归或大的递归深度时。它需要仔细处理基本情况和逻辑。

空间复杂度

由于递归中的调用堆栈，它可能导致大量的内存消耗。