登录以参加训练计划

# C++ 函数与递归核心知识总结

---

## 一、函数基础

### 1. 函数的作用
- **代码复用**：封装重复操作的代码块
- **模块化**：将复杂问题分解为多个子任务
- **易维护**：修改函数逻辑不影响其他代码
- **参数传递**：实现数据输入输出的灵活控制

### 2. 函数定义与调用
```cpp
// 定义语法
返回值类型 函数名(参数列表) {
    函数体
    return 表达式; // void函数可省略
}

// 示例：比较两个数的大小
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 调用示例
int result = max(5, 3); // result = 5

3. 参数传递机制

类型	特点	示例
形参	函数定义时声明的参数	void func(int x)
实参	调用时实际传入的值	func(10)
引用传递	使用&直接操作原变量	void swap(int &a, int &b)

引用传递示例：

void swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

int main() {
    int a=3, b=5;
    swap(a, b);  // 实际交换了a,b的值
    cout << a << b; // 输出53
}

---

二、递归详解

1. 递归定义

• 本质：函数直接或间接调用自身
• 必要条件：
  1. 递归关系：问题可分解为同类子问题
  2. 终止条件：存在明确的递归出口

2. 递归解题四步法

1. 确定递归边界：找到最小子问题的解
2. 提取递归关系：建立n与n-1的递推式
3. 设计参数传递：确定需要传递的状态参数
4. 验证正确性：通过简单案例测试

3. 经典递归模板

返回类型 递归函数(参数){
    if(终止条件) return 基准解;
    
    // 递推操作
    处理当前层逻辑;
    
    // 递归调用
    递归函数(缩小问题规模);
    
    // 回归操作（可选）
    处理子问题返回结果;
}

4. 递归优化策略

策略	说明	示例场景
记忆化	存储已计算结果避免重复计算	斐波那契数列
尾递归	将递归调用放在函数最后一步	阶乘计算
剪枝	提前终止无效递归分支	组合数计算

5. 递归与循环对比

特性	递归	循环
实现方式	函数自调用	迭代语句
内存消耗	栈空间消耗大	固定内存消耗
可读性	数学关系清晰	流程直观
适用场景	树形结构、分治问题	线性遍历、计数操作

---

三、CSP-J 高频考点

1. 必会递归题型

1. 数列计算：斐波那契数列、阶乘
2. 数位处理：十进制转二进制、数字反转
3. 组合问题：全排列、子集生成
4. 分治算法：归并排序、快速排序

2. 常见错误预警

• 栈溢出：递归深度超过系统限制（通常约1e4层）
• 死递归：缺少/错误的终止条件
• 参数污染：错误修改全局变量
• 重复计算：未记忆化导致指数级时间复杂度

四、实战训练题

1. 递归实现数字各位求和（如1234→1+2+3+4=10）
2. 用递归判断回文数
3. 递归生成二进制表示（如5→101）
4. 递归计算最大公约数（GCD）

// 示例：数字各位求和
int digitSum(int n) {
    if(n < 10) return n;
    return n%10 + digitSum(n/10);
}

建议练习时先画递归调用图，再编写代码验证