04 函数与递归

GESP 4-5 级CSP-J 核心

级别标注：GESP 4 级（函数）/ 5 级（递归）（考级要求）/ CSP-J 核心（竞赛进阶，递归是搜索与分治的地基）。

一、函数的基本定义与调用

C++ 实例
#include <iostream>
using namespace std;

// 求两数最大公约数（辗转相除法：gcd(a,b) = gcd(b, a%b)）
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);   // 余数为 0 时返回除数
}

// 返回 int 类型的函数：两数相加
int add(int x, int y) {
    return x + y;                        // 把计算结果返回给调用处
}

// void 表示无返回值，只执行操作（这里打印一行横线）
void printLine(int n) {
    for (int i = 0; i < n; i++) cout << "-";   // 连续输出 n 个 '-'
    cout << endl;                        // 换行
}

int main() {
    cout << add(3, 4) << endl;           // 调用 add，输出 7
    cout << gcd(12, 18) << endl;         // 输出 6
    printLine(20);                       // 打印 20 个横线
    return 0;                            // 正常结束
}

函数四要素：返回类型、函数名、参数列表、函数体。

形象理解函数像餐厅的标准化菜谱：int add(int x, int y) 就是“收两份食材 x、y，按固定步骤加工，端出一份 int 菜”。void 表示“只负责干活不上菜”（无返回值）。
考级视角GESP 4 级要求掌握：函数定义/调用/返回值、形参与实参、局部变量与全局变量。读程序题常考“形参改名后实参变不变”——默认值传递，改形参不影响实参。

二、参数传递方式

2.1 值传递（默认）：拷贝一份，不影响原变量

C++ 实例
#include <iostream>
using namespace std;

// 值传递：形参 x 是实参的"复印件"
void f(int x) {
    x = 100;            // 只修改复印件，不影响外面的变量
}

int main() {
    int a = 1;
    f(a);               // 传入的是 a 的拷贝
    cout << a << endl;  // 仍为 1（原件未被修改）
    return 0;
}

2.2 引用传递（&）：直接操作原变量

C++ 实例
#include <iostream>
using namespace std;

// 引用传递：形参 &x、&y 是实参的"别名"，直接操作原件
void swap2(int &x, int &y) {
    int t = x;          // 先把 x 的值存入临时变量
    x = y;              // x 变成 y
    y = t;              // y 变成原来的 x
}

int main() {
    int a = 3, b = 5;
    swap2(a, b);                        // 引用参数会真实交换 a、b
    cout << a << " " << b << endl;      // 输出 5 3
    return 0;
}

函数模板注意事项：函数定义必须出现在调用前，或先用"函数声明/原型"：

C++ 实例
#include <iostream>
#include <algorithm>
using namespace std;

int max3(int, int, int);   // 函数原型（声明）：先告诉编译器"存在这个函数"

int main() {
    cout << max3(1, 9, 4) << endl;   // 调用时编译器已知其签名
    return 0;
}

// 定义可以放在 main 之后（只要之前有声明即可）
int max3(int a, int b, int c) {
    return max(a, max(b, c));        // 先取 b、c 较大者，再与 a 比较
}
形象理解值传递像复印身份证：函数拿到复印件随便改，原件不受影响；引用传递（&）像把原件直接递进去，函数一改原件就变。想交换两个变量的值，必须用引用或指针。
易错点交换两个数用 void swap2(int &x, int &y)；如果漏写 &，交换只在函数内生效，调用后 a、b 原封不动——这是新手写排序代码时最常见的“换了等于没换”。

三、函数重载（同名不同参）

C++ 实例
#include <iostream>
using namespace std;

// 函数重载：同名函数，靠参数类型区分调用哪个版本
int sum(int a, int b) { return a + b; }          // int 版本
double sum(double a, double b) { return a + b; } // double 版本

int main() {
    cout << sum(1, 2) << endl;        // 传 int → 调用 int 版 → 3
    cout << sum(1.5, 2.5) << endl;    // 传 double → 调用 double 版 → 4
    return 0;
}
形象理解函数重载像同名的多合一工具：sum(1, 2) 自动选 int 版本，sum(1.5, 2.5) 自动选 double 版本——编译器根据参数类型“认人下菜”。
易错点重载只认参数类型和个数，不认返回值类型：int f() 和 double f() 同时存在会编译报错。也不要写参数能互相隐式转换的暧昧重载，容易调用歧义。

四、递归基础

递归 = 函数调用自身。必须满足： 1. 终止条件（基准情形，否则无限递归爆栈）。 2. 规模递减（每步向终止条件靠近）。

4.1 阶乘

C++ 实例
// 递归求阶乘：n! = n × (n-1)!
long long fact(int n) {
    if (n <= 1) return 1;             // 基准情形：0! = 1! = 1
    return n * fact(n - 1);           // 递归调用：规模每次减 1
}
// 执行过程：fact(5) = 5 * fact(4) = 5*4*3*2*1 = 120

4.2 斐波那契（朴素递归，用于理解递归，竞赛会优化）

C++ 实例
// 朴素递归斐波那契：第 n 项 = 前两项之和
long long fib(int n) {
    if (n <= 2) return 1;                       // 基准：fib(1)=fib(2)=1
    return fib(n - 1) + fib(n - 2);             // 拆成两个更小的子问题
}
// 注意：朴素写法会重复计算大量子问题，n 大时极慢（竞赛用记忆化/DP，见 15 章）

⚠️ 朴素 fib(45) 会非常慢（指数级重复计算），竞赛中需用"记忆化"或 DP（详见 15 章）。

4.3 递归执行过程的理解（以 fact(4) 为例）

示例
fact(4)
 -> 4 * fact(3)
      -> 3 * fact(2)
           -> 2 * fact(1) = 2
      = 3 * 2 = 6
 = 4 * 6 = 24

理解要点：先"递下去"（不断压栈），到基准后"归回来"（依次出栈计算并返回）。

形象理解递归像俄罗斯套娃：打开最大的娃娃，里面是稍小的娃娃，直到最小的那个“终止娃娃”。每次打开都在“递”，打开到底再一层层“归”回来组装答案。没有终止娃娃就是无限套娃（爆栈）。
考级视角GESP 5 级考递归求阶乘、斐波那契、汉诺塔；要求能手推递归执行过程。建议用“压栈/出栈”画图法：每一层调用就是往栈顶压一层，返回值时再弹出来。

五、递归经典应用

5.1 汉诺塔

C++ 实例
#include <iostream>
using namespace std;

// 汉诺塔：把 n 个盘子从 from 柱借助 aux 柱移到 to 柱
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {                       // 只剩一个盘子：直接移动
        cout << from << " -> " << to << endl;
        return;
    }
    // 三步走：先把上面 n-1 个挪开，再移最大盘
    hanoi(n - 1, from, aux, to);        // 1) 把 n-1 个小盘 from→aux
    cout << from << " -> " << to << endl;   // 2) 最大盘 from→to
    hanoi(n - 1, aux, to, from);        // 3) 把 n-1 个小盘 aux→to
}

int main() {
    hanoi(3, 'A', 'C', 'B');            // 3 个盘子从 A 移到 C，B 作辅助
    return 0;
}

5.2 指数计算（快速幂见 16 章）

C++ 实例
// 普通递归求 a^n：a^n = a × a^(n-1)
long long power(int a, int n) {
    if (n == 0) return 1;               // 基准：任何数的 0 次方为 1
    return a * power(a, n - 1);         // 指数每次减 1，共递归 n 层
}
// 进阶：快速幂用"指数折半"把层数降到 O(log n)，见 16 章

5.3 全排列（回溯，详见 14 章）

C++ 实例
#include <iostream>
using namespace std;
const int N = 10;
int n, a[N];          // a 存当前排列（正在构造的结果）
bool used[N];         // used[i] 标记数字 i 是否已被使用

void perm(int k) {    // 正在填第 k 个位置
    if (k == n) {                       // 所有位置填满：输出一个排列
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {      // 尝试把 1~n 中未用的数字放到第 k 位
        if (!used[i]) {
            used[i] = true;             // 进入前标记：占用数字 i
            a[k] = i;                   // 第 k 位放 i
            perm(k + 1);                // 递归填下一位
            used[i] = false;            // 返回后撤销标记（回溯）
        }
    }
}

int main() {
    cin >> n;
    perm(0);                            // 从第 0 位开始填
    return 0;
}
形象理解汉诺塔像搬家工人：想搬 n 个箱子，先请人把上面 n-1 个搬到临时位置，自己搬最重的大箱子，再请人把 n-1 个搬回目标位。自己只搬一个，其余交给“递归分身”。
易错点全排列回溯最容易漏掉“撤销标记”：used[i] = false; 必须写，否则下一层分支会看到被污染的标记，输出排列不全。口诀：标记 → 递归 → 撤销。

六、易错点 / 常见坑点

  • ⚠️ 忘记终止条件 → 栈溢出 stack overflow / 死递归。
  • ⚠️ 递归层数过深（如超过 10 万层）可能爆栈，C++ 默认栈空间有限，竞赛大递归常用"迭代/循环"或加大栈空间。
  • ⚠️ 递归+全局变量要小心"进入递归修改、回溯忘记还原"。
  • ⚠️ 值传递与引用传递混淆：想在函数里改外层变量必须用 &。
  • ⚠️ 局部变量出了函数就销毁，别返回局部数组/局部 string 的指针（undefined behavior）。
  • ⚠️ 函数声明顺序：调用前必须"见过"声明或定义。

七、考级要求 vs 竞赛进阶

  • 考级要求：函数定义/调用/返回值、形参实参、作用域（GESP 4 级）；递归求阶乘、斐波那契、汉诺塔（GESP 5 级）。
  • 竞赛进阶（CSP-J/NOIP）：递归是DFS、分治、回溯、归并排序的共同底座；要求理解调用栈、会用全局数组代替大量局部拷贝、重构大递归。

八、课内练习建议

  1. 用递归求 1+2+...+n。
  2. 递归求解最大公约数（辗转相除）。
  3. 递归判断回文串。
  4. 递归求 n 个数的最大值。
  5. 理解并手写一遍汉诺塔的移动过程（n=3 共 7 步）。
本章目录
一、函数的基本定义与调用 二、参数传递方式 三、函数重载（同名不同参） 四、递归基础 五、递归经典应用 六、易错点 / 常见坑点 七、考级要求 vs 竞赛进阶 八、课内练习建议