递归函数通过自身调用解决可分解的子问题，需明确定义终止条件和调用逻辑，如阶乘和斐波那契数列。
递归函数是C++中一种通过函数调用自身来解决问题的方法。它特别适用于可以分解为相同类型子问题的场景，比如阶乘计算、斐波那契数列、树的遍历等。使用递归的关键是定义清楚递归终止条件和递归调用逻辑，否则可能导致无限调用或栈溢出。
递归的基本语法结构
在C++中定义递归函数，语法和普通函数一样，但函数体内包含对自身的调用。基本结构如下：
返回类型 函数名(参数) {
if (终止条件) {
return 终止值;
}
// 递归调用
return 函数名(更新后的参数);
}
例如，计算n的阶乘：
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
这里，n == 0 || n == 1 是终止条件，避免无限递归。
立即学习“C++免费学习笔记（深入）”；
解决实际问题：斐波那契数列
斐波那契数列定义为：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。用递归实现非常直观：
int fibonacci(int n) {
if (n
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
虽然这种写法简洁，但存在重复计算问题，效率较低。可通过记忆化（如用数组保存已计算结果）优化。
递归在数据结构中的应用：二叉树遍历
递归非常适合处理树形结构。例如，前序遍历二叉树：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void preorder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " "; // 访问根节点
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
递归天然匹配树的结构，代码清晰易懂。
使用递归的注意事项
递归虽然简洁，但需要注意以下几点：
- 必须设置明确的终止条件，防止无限递归
- 递归深度过大可能导致栈溢出，尤其是处理大规模数据时
- 某些递归实现效率低，如朴素斐波那契，可考虑用动态规划或迭代优化
- 每次函数调用都有额外开销，包括参数压栈和返回地址保存
基本上就这些。掌握递归的核心是理解“问题分解”和“边界控制”，写多了就熟练了。
