C++递归简介

• 递归的定义：递归是指在函数的定义中使用函数自身的方法。一个递归函数通常包含两部分：基线条件（base case）和递归条件（recursive case）。基线条件用于终止递归，防止无限循环；递归条件则定义了如何通过调用自身来逐步解决问题，将大问题分解为更小的同类型子问题。
• 递归的调用栈：当一个递归函数被调用时，系统会为每次调用创建一个新的栈帧，把函数的参数、局部变量等信息压入栈中。随着递归的深入，栈帧不断堆积，当达到基线条件后，函数开始层层返回，栈帧逐个弹出，直到回到最初的调用点。

2. 简单递归例子：阶乘函数
   • 原理：阶乘的数学定义是 (n! = n \times (n - 1) \times \cdots \times 1)，可以用递归方式实现，其中 (n = 0) 或 (n = 1) 时，(n! = 1) 作为基线条件，其余情况通过 (n \times (n - 1)!) 进行递归调用。
   • 代码示例：

int factorial(int n) {if (n == 0 || n == 1) {return 1;}return n * factorial(n - 1);
}

• 调用示例：

int main() {int num = 5;int result = factorial(num);std::cout << num << " 的阶乘是: " << result << std::endl;return 0;
}

3. 斐波那契函数
   • 原理：斐波那契数列的定义是 (F(n)=F(n - 1)+F(n - 2))，其中 (F(0)=0)，(F(1)=1) 为基线条件，后续的数通过前两项相加得出。
   • 代码示例：

int fibonacci(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return fibonacci(n - 1) + fibonacci(n - 2);
}

• 调用示例：

int main() {int index = 6;int value = fibonacci(index);std::cout << "斐波那契数列第 " << index << " 项是: " << value << std::endl;return 0;
}

4. 检测回文
   • 原理：回文是指正读和反读都一样的字符串或序列。对于字符串，可以通过比较首尾字符，然后递归地检查剩余中间部分是否为回文来实现。基线条件可以是字符串长度小于等于 1 时，它必然是回文。
   • 代码示例：

#include <string>
#include <iostream>bool isPalindrome(const std::string& str) {int length = str.length();if (length <= 1) {return true;}if (str[0]!= str[length - 1]) {return false;}return isPalindrome(str.substr(1, length - 2));
}

• 调用示例：

int main() {std::string test = "madam";if (isPalindrome(test)) {std::cout << test << " 是回文" << std::endl;} else {std::cout << test << " 不是回文" << std::endl;}return 0;
}

5. 二分查找算法
   • 原理：二分查找用于在有序数组中查找目标元素。每次将数组分成两部分，比较中间元素与目标元素的大小，若相等则找到；若目标元素小于中间元素，则在左半部分继续查找，反之在右半部分查找。基线条件是查找区间为空时，说明未找到。
   • 代码示例：

#include <iostream>
#include <vector>int binarySearch(const std::vector<int>& arr, int target, int left, int right) {if (left > right) {return -1;}int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] > target) {return binarySearch(arr, target, left, mid - 1);} else {return binarySearch(arr, target, mid + 1, right);}
}

• 调用示例：

int main() {std::vector<int> numbers = {1, 3, 5, 7, 9};int target = 5;int result = binarySearch(numbers, target, 0, numbers.size() - 1);if (result!= -1) {std::cout << "找到目标元素，位置是: " << result << std::endl;} else {std::cout << "未找到目标元素" << std::endl;}return 0;
}

6. 间接递归
   • 原理：间接递归指的是函数 (A) 调用函数 (B)，而函数 (B) 又调用函数 (A)。要实现间接递归，需要在两个函数的定义中都有合适的基线条件，防止无限循环。
   • 代码示例：

#include <iostream>void functionA(int n);
void functionB(int n);void functionA(int n) {if (n > 0) {std::cout << n << " ";functionB(n - 1);}
}void functionB(int n) {if (n > 0) {std::cout << n << " ";functionA(n - 1);}
}

• 调用示例：

int main() {functionA(3);return 0;
}

7. 递归的思考
   • 优点：递归代码往往能简洁直观地表达复杂的数学定义或分治思想，代码结构与问题的逻辑结构相似，易于理解和编写，尤其是处理树形、图状结构等具有递归性质的数据结构时。
   • 缺点：递归调用会消耗大量的栈空间，因为每次调用都要创建新的栈帧，对于深度较大的递归，可能导致栈溢出错误。而且递归函数的执行效率有时不如迭代解法，因为递归涉及函数调用开销，而迭代可以通过循环更紧凑地执行相同逻辑。在实际编程中，对于一些简单的递归问题，如阶乘、斐波那契数列，若性能要求高，可以考虑用迭代方式重写，利用动态规划等优化策略来减少重复计算。
     

递归和迭代的区别

1. 概念本质

   • 递归
     • 递归是一种函数调用自身的编程技巧。它将一个复杂的问题逐步分解为规模更小的相同问题，直到达到一个可以直接求解的基本情况（基线条件）。这种分解过程是通过不断地自我调用来实现的，就像层层嵌套的俄罗斯套娃，每一层都在处理一个相似但规模更小的任务。
     • 例如，计算阶乘的递归函数factorial(n)，它在n > 1时通过n * factorial(n - 1)不断调用自身来计算n!，直到n等于0或1（基线条件），此时直接返回1。
   • 迭代
     • 迭代是通过循环结构（如for循环、while循环）来重复执行一段代码，直到满足某个终止条件。它基于一个初始状态，按照一定的规则逐步更新状态，每次更新都是在前一次的基础上进行的，就像沿着一条路径一步一步前进，直到到达目的地。
     • 同样以计算阶乘为例，迭代的方式是从1开始，通过一个循环不断乘以从2到n的数字，逐步计算出n!。

2. 实现方式与代码结构

   • 递归
     • 代码结构特点：递归函数的代码结构通常比较简洁和直观，尤其是对于具有递归性质的数学定义或分治算法。它的代码逻辑往往直接反映了问题的递归定义。
     • 示例 - 斐波那契数列（递归）：

     int fibonacci(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return fibonacci(n - 1) + fibonacci(n - 2);
     }
     

     在这个例子中，代码直接按照斐波那契数列的定义来编写，通过不断调用自身来计算数列中的值。但是，这种方式会存在重复计算的问题，例如计算fibonacci(5)时，fibonacci(3)会被多次计算。
   • 迭代
     • 代码结构特点：迭代的代码通常包含循环结构，可能会有一个或多个变量来记录状态。代码看起来更像是一系列按顺序执行的指令，通过更新变量和检查条件来控制循环的执行。
     • 示例 - 斐波那契数列（迭代）：

     int fibonacci(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}int a = 0, b = 1, result;for (int i = 2; i <= n; ++i) {result = a + b;a = b;b = result;}return result;
     }
     

     这里使用循环来逐步计算斐波那契数列的值，通过变量a、b和result来记录中间状态，避免了递归方式中的重复计算。

3. 性能和资源消耗

   • 时间复杂度
     • 递归：递归函数的时间复杂度可能会因为重复计算而变得很高。例如，在上述斐波那契数列的递归实现中，时间复杂度是指数级的(O(2^n))，因为在计算过程中，许多子问题会被多次计算。不过，有些递归算法可以通过记忆化（Memoization）等技术来避免重复计算，降低时间复杂度。
     • 迭代：迭代算法的时间复杂度通常更容易分析和控制。对于斐波那契数列的迭代实现，时间复杂度是线性的(O(n))，因为它只需要按照顺序执行n次循环就可以得到结果。
   • 空间复杂度
     • 递归：递归函数在调用过程中会占用大量的栈空间。每次函数调用都会在栈上创建一个新的栈帧，用于存储函数的参数、局部变量和返回地址等信息。对于深度较大的递归，可能会导致栈溢出（Stack Overflow）。例如，在计算较大的斐波那契数时，递归调用的栈深度可能会很深，消耗大量栈空间。
     • 迭代：迭代算法通常只需要使用有限的额外空间来存储循环变量等信息，空间复杂度相对较低。在斐波那契数列的迭代实现中，除了几个用于记录状态的变量外，不需要额外的大量空间，空间复杂度是(O(1))（不考虑结果存储所需的空间）。

4. 适用场景

   • 递归
     • 适合场景：递归非常适合处理具有递归结构的数据结构，如树和图。例如，在树的遍历（如前序遍历、中序遍历、后序遍历）中，递归可以很自然地表达遍历的过程。同时，对于一些问题，递归的实现方式能够更清晰地体现问题的本质和逻辑，使得代码易于理解和编写，特别是当问题的递归定义很明确时，如汉诺塔问题。
     • 不适合场景：当问题规模较大，递归深度可能很深，且没有有效的优化措施（如记忆化）时，递归可能会导致性能问题和栈溢出。此外，对于一些对性能要求极高的场景，如实时系统或嵌入式系统中的某些关键算法，递归可能不是最佳选择，因为其函数调用开销和潜在的高时间复杂度可能会影响系统性能。
   • 迭代
     • 适合场景：迭代适用于大多数可以通过循环逐步解决的问题，特别是当问题可以被描述为一个重复的过程，且不需要像递归那样层层分解问题时。例如，数值计算（如求和、求积）、遍历线性数据结构（如数组、链表）等场景，迭代通常是一种高效的实现方式。
     • 不适合场景：当问题的结构比较复杂，难以用简单的循环来表达时，迭代可能会使代码变得复杂和难以理解。例如，对于一些具有复杂递归结构的问题，如某些树形结构的复杂操作，如果用迭代来实现，可能需要手动维护栈等数据结构来模拟递归的调用过程，这会增加代码的复杂性。