递归法
递归法是一种常用的算法思想，其核心思想是将一个问题分解成更小的子问题来求解。递归法通常包含两个要素：递归边界和递归公式。
递归边界是指问题可以直接求解的情况，也就是递归调用停止的条件。递归公式是指将问题分解成更小的子问题的公式，通常包含一个或多个递归调用。
下面是一个使用递归法求解阶乘的例子。阶乘是指一个数$n$的阶乘等于$1\\times 2\\times\\cdots\\times n$，用符号表示为$n!$。
#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n-1);
}
}
int main() {
int n;
cin >> n;
cout << factorial(n) << endl;
return 0;
}在这个例子中，我们使用了递归法求解阶乘。递归边界是$n=0$或$n=1$的情况，此时阶乘的值为1。递归公式是$n!=n\\times (n-1)!$，即问题可以分解为计算$(n-1)!$并乘以$n$。
在代码中，我们使用了一个函数factorial来计算$n$的阶乘。如果$n$等于0或1，那么函数直接返回1；否则，函数返回$n$乘以调用factorial函数计算$n-1$的阶乘的结果。递归调用的过程中，每个函数都会创建一个新的栈帧，保存函数的局部变量和参数。当递归调用结束时，栈帧会被弹出，控制权返回到上一级函数。
需要注意的是，在使用递归法求解问题时，可能会出现栈溢出的问题。这是因为递归调用会创建大量的栈帧，如果递归深度过大，栈空间可能会耗尽。因此，在编写递归函数时，需要仔细考虑递归深度和栈空间的使用情况，以避免出现栈溢出等问题。
下面再举一个例子，使用递归法来实现二分查找算法。二分查找是一种在有序数组中查找特定元素的算法，其核心思想是通过对比中间元素和目标元素的大小关系，将查找范围缩小一半，直到找到目标元素或者查找范围为空。
#include <iostream>
#include <vector>
using namespace std;
int binary_search(vector<int>& nums, int target, int left, int right) {
if (left > right) {
return -1; // 递归边界：未找到目标元素
}
int mid = left + (right - left) / 2; // 计算中间位置
if (nums[mid] == target) {
return mid; // 递归边界：找到目标元素
} else if (nums[mid] > target) {
return binary_search(nums, target, left, mid-1); // 递归公式：在左半部分查找
} else {
return binary_search(nums, target, mid+1, right); // 递归公式：在右半部分查找
}
}
int main() {
vector<int> nums = {1, 3, 5, 7, 9};
int target = 7;
int result = binary_search(nums, target, 0, nums.size()-1);
if (result == -1) {
cout << "Target not found" << endl;
} else {
cout << "Target found at index " << result << endl;
}
return 0;
}在这个例子中，我们使用递归法实现了二分查找算法。递归边界是left>right的情况，此时表示查找范围为空，未找到目标元素；另一个递归边界是nums[mid]=target的情况，此时表示找到了目标元素。递归公式是根据中间元素与目标元素的大小关系，将查找范围缩小一半，分别在左半部分或右半部分查找。
需要注意的是，在使用递归法求解问题时，递归深度会影响算法的效率。递归深度过深会导致栈空间的耗尽，从而影响程序的运行效率。因此，在编写递归函数时，需要仔细考虑递归深度和栈空间的使用情况，以避免出现效率问题。同时，递归法也常常可以使用迭代法等其他算法思想来替代，以提高算法的效率。
下面再介绍一个例子，使用递归法实现斐波那契数列。斐波那契数列是一个数列，其中每个数字都是前两个数字之和，起始数字为0和1。数列中的前几个数字依次为0、1、1、2、3、5、8、13、21、34等。
斐波那契数列可以使用递归法来实现，递归边界是前两个数字，即0和1，递归公式是每个数字等于前两个数字之和。
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n == 0) {
return 0; // 递归边界：第0个数字为0
} else if (n == 1) {
return 1; // 递归边界：第1个数字为1
} else {
return fibonacci(n-1) + fibonacci(n-2); // 递归公式：每个数字等于前两个数字之和
}
}
int main() {
int n = 10;
for (int i = 0; i <= n; i++) {
cout << fibonacci(i) << " ";
}
cout << endl;
return 0;
}在这个例子中，我们使用递归法实现了斐波那契数列。递归边界是n=0和n=1的情况，此时分别返回0和1。递归公式是每个数字等于前两个数字之和。在主函数中，我们输出了斐波那契数列的前10个数字。
需要注意的是，斐波那契数列的递归实现效率较低，因为在计算fibonacci(n)时，会重复计算fibonacci(n-1)和fibonacci(n-2)。这些重复计算会导致递归深度较深，从而影响程序的运行效率。为了避免这个问题，我们可以使用递推法或动态规划等其他算法思想来优化斐波那契数列的计算。
下面再给出一个例子，使用递归法实现二叉树的遍历。二叉树是一种树形结构，每个节点最多有两个子节点，称为左子节点和右子节点。二叉树的遍历有三种方式，分别是前序遍历、中序遍历和后序遍历。
以前序遍历为例，前序遍历的顺序是先遍历根节点，然后递归遍历左子树和右子树。二叉树的前序遍历可以使用递归法实现，递归公式是先输出当前节点，然后递归遍历左子树和右子树。
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return; // 递归边界：节点为空
}
cout << root->val << " "; // 输出当前节点
preorderTraversal(root->left); // 递归遍历左子树
preorderTraversal(root->right); // 递归遍历右子树
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
preorderTraversal(root);
cout << endl;
return 0;
}在这个例子中，我们定义了一个TreeNode结构体，包含节点的值和左右子节点。然后，我们使用递归法实现了二叉树的前序遍历。递归边界是节点为空的情况，此时直接返回。递归公式是先输出当前节点，然后递归遍历左子树和右子树。在主函数中，我们构建了一个二叉树，并输出了它的前序遍历结果。
需要注意的是，递归法在实现二叉树遍历时，可能会导致递归深度过深，从而导致栈溢出的问题。为了避免这个问题，我们可以使用非递归的迭代法来实现二叉树的遍历，这个方法可以使用栈来模拟递归的过程，从而避免递归深度过深的问题。
斐波那契数列是一个非常经典的数列，定义如下：
$$f_0=0,f_1=1$$
$$f_n=f_{n-1}+f_{n-2} \\qquad (n\\geq 2)$$
也就是说，每个数都是前两个数的和，如下所示：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
我们可以使用递归法来实现斐波那契数列，递归公式是 $f_n=f_{n-1}+f_{n-2}$，递归边界是 $f_0=0,f_1=1$。代码如下：
#include <iostream>
using namespace std;
int fib(int n) {
if (n == 0) {
return 0; // 递归边界：f(0)=0
}
if (n == 1) {
return 1; // 递归边界：f(1)=1
}
return fib(n - 1) + fib(n - 2); // 递归公式：f(n)=f(n-1)+f(n-2)
}
int main() {
for (int i = 0; i < 10; ++i) {
cout << fib(i) << " ";
}
cout << endl;
return 0;
}在这个例子中，我们使用递归法实现了斐波那契数列。递归边界是 $f_0=0,f_1=1$，此时直接返回。递归公式是 $f_n=f_{n-1}+f_{n-2}$，在求 $f_n$ 时，我们需要递归求解 $f_{n-1}$ 和 $f_{n-2}$。在主函数中，我们输出了斐波那契数列的前10项。
需要注意的是，递归法在实现斐波那契数列时，效率比较低，因为每个数都会被计算多次。比如，计算 $f_5$ 时，会重复计算 $f_3$，计算 $f_4$ 时，也会重复计算 $f_3$。这种重复计算的现象，称为重复子问题。如果使用动态规划的方法，可以避免重复子问题的计算，从而提高计算效率。
