第3章：函数和递归（Functions and Recursion）

一、导读

3.1 本章学习目标

第3章标志着从"写代码"到"设计程序"的跃升。前两章我们关注的是如何用变量、数组和控制流表达计算过程；本章则要解决一个更高层次的问题：如何组织代码，使其清晰、可复用、可维护。函数是代码组织的基本单元，而递归则是一种强大的问题求解策略——它不仅是编程技巧，更是一种思维方式。

本章的核心学习目标包括：

掌握函数的定义与调用：理解参数传递、返回值、作用域等核心概念。
深入理解递归的本质：递归是函数调用自身，其执行过程对应着调用栈的展开和折叠。
学会分治思想：将大问题分解为小问题，递归求解后合并结果。
理解记忆化搜索：通过缓存递归结果避免重复计算，这是动态规划的雏形。
掌握递归到迭代的转换：理解递归的开销，学会用栈或循环替代递归。
认识递归的局限性：栈溢出的风险，以及如何通过尾递归优化或手动栈来规避。

3.2 为什么本章如此重要

递归在算法竞赛中的地位怎么强调都不为过。后续章节中几乎所有重要算法都依赖递归：分治排序（归并、快排）、树的遍历、深度优先搜索（DFS）、动态规划的记忆化搜索、回溯法求解组合问题……这些算法的核心模式都是"函数调用自身"。

但递归不仅仅是技巧。递归思维的本质是将复杂问题分解为结构相同的子问题。这种"分而治之"的思想贯穿了整个计算机科学。当你面对一个看似复杂的问题时，如果你能发现它的子结构和自相似性，递归就是最自然的表达方式。

函数则是代码质量的保障。在竞赛中，良好的函数设计可以让你快速调试、复用代码、减少错误。一个写得好的函数，输入输出明确，逻辑独立，可以被反复调用而不会产生副作用。

3.3 核心问题引导

在阅读本章时，请带着以下问题思考：

函数调用时，参数是如何传递的？值传递和引用传递有什么区别？

递归函数的执行过程是怎样的？调用栈在其中扮演什么角色？

为什么每个递归函数都必须有"终止条件"？没有终止条件会怎样？

斐波那契数列的朴素递归为什么效率极低？如何用记忆化来解决？

分治策略的核心是什么？归并排序是如何体现分治思想的？

什么时候应该用递归，什么时候应该用迭代？如何权衡？

二、核心概念详解

3.1 函数

3.1.1 函数的定义与调用

函数是一段具有特定功能的、可复用的代码块。它接受输入（参数），执行计算，返回输出（返回值）：

// 函数定义
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 函数调用
int x = 5, y = 3;
int m = max(x, y);  // m = 5

函数签名（返回类型 + 参数列表）是函数的接口。好的函数设计应该有清晰的接口：

// 好的设计：函数名表达功能，参数含义明确
int count_primes(int n);         // 计算 1~n 中素数的个数
bool is_palindrome(const char *s); // 判断字符串是否为回文

// 差的设计：函数名模糊，参数含义不清
int calc(int *a, int n, int x);  // 这个函数到底做什么？

3.1.2 参数传递

C 语言的参数传递是值传递（pass by value）——函数收到的是参数的副本，修改参数不会影响原始变量：

void swap_wrong(int a, int b) {
    int t = a; a = b; b = t;  // 只交换了副本，原始变量不变！
}

// 正确做法：传递指针
void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int x = 1, y = 2;
swap(&x, &y);  // x = 2, y = 1

在 C++ 中，可以使用引用传递，语法更简洁：

cpp

void swap(int &a, int &b) {
    int t = a; a = b; b = t;
}

int x = 1, y = 2;
swap(x, y);  // 不需要 &

3.1.3 局部变量与全局变量

int global_var = 100;  // 全局变量：所有函数可见

void func() {
    int local_var = 200;  // 局部变量：只在 func 内可见
    global_var = 300;     // 可以修改全局变量
}

int main() {
    func();
    printf("%d\n", global_var);  // 300
    // printf("%d\n", local_var); // 错误！local_var 在 main 中不可见
    return 0;
}

竞赛建议：尽量少用全局变量。全局变量会导致函数之间的隐式依赖，增加调试难度。如果必须使用（比如大数组放在全局以避免栈溢出），要用注释说明其用途。

3.1.4 函数声明与头文件

C/C++ 要求函数在使用前必须声明（或定义）：

// 函数声明（前向声明）
int gcd(int a, int b);

// 在 main 中调用
int main() {
    printf("%d\n", gcd(12, 8));  // 4
    return 0;
}

// 函数定义
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

3.2 递归

3.2.1 递归的基本模型

递归函数是调用自身的函数。每个递归函数都必须包含两个要素：

终止条件（base case）：不再递归的条件

递归步骤（recursive step）：将问题缩小，最终导向终止条件

// 阶乘：n! = n * (n-1)!
long long factorial(int n) {
    if (n <= 1) return 1;       // 终止条件
    return n * factorial(n - 1); // 递归步骤
}

3.2.2 递归的执行过程——调用栈

当函数被调用时，系统会在调用栈（call stack）上分配一个栈帧（stack frame），保存局部变量、参数和返回地址。递归调用时，每次调用都会创建新的栈帧：

factorial(4) 的调用过程：

factorial(4)
  → 4 * factorial(3)
       → 3 * factorial(2)
            → 2 * factorial(1)
                 → return 1          ← 终止条件
            → return 2 * 1 = 2
       → return 3 * 2 = 6
  → return 4 * 6 = 24

栈帧的展开和折叠就像一摞盘子：调用时往上叠（push），返回时往下取（pop）。

3.2.3 栈溢出

每次递归调用都需要栈帧空间。如果递归深度过大，栈空间会耗尽，导致栈溢出（Stack Overflow）：

// 危险的递归：n 很大时会栈溢出
void dangerous(int n) {
    int big_array[10000];  // 每个栈帧占用 40KB
    dangerous(n - 1);      // 无限递归（没有终止条件）
}

一般程序的栈空间为 1~8 MB。如果每次递归的栈帧大小为 32 字节，递归深度达到 10⁵ 就可能溢出。在竞赛中，如果递归深度可能超过 10⁴，要考虑改用迭代或手动模拟栈。

3.2.4 经典递归案例

汉诺塔：将 n 个盘子从 A 柱移到 C 柱，每次只能移动一个盘子，且大盘不能放在小盘上面。

void hanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    hanoi(n - 1, from, aux, to);      // 将 n-1 个盘子从 from 移到 aux
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);      // 将 n-1 个盘子从 aux 移到 to
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

全排列：生成 1~n 的所有排列。

int perm[10], used[10], n;

void generate(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i++)
            printf("%d ", perm[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = 1;
            perm[pos] = i;
            generate(pos + 1);
            used[i] = 0;  // 回溯
        }
    }
}

3.3 分治思想

3.3.1 分治的三步

分治（Divide and Conquer）策略的核心步骤：

分解（Divide）：将问题分成若干个规模更小的子问题

解决（Conquer）：递归地求解子问题

合并（Combine）：将子问题的解合并为原问题的解

3.3.2 归并排序

归并排序是分治策略的经典应用：

void merge_sort(int *a, int l, int r) {
    if (r - l <= 1) return;  // 终止条件：区间长度 ≤ 1
    
    int mid = l + (r - l) / 2;
    merge_sort(a, l, mid);   // 分治：排序左半部分
    merge_sort(a, mid, r);   // 分治：排序右半部分
    
    // 合并两个有序部分
    int tmp[r - l], i = l, j = mid, k = 0;
    while (i < mid && j < r)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i < mid) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int i = 0; i < k; i++) a[l + i] = tmp[i];
}

时间复杂度：T(n) = 2T(n/2) + O(n) = O(n log n)。

3.4 记忆化搜索

3.4.1 重复计算的问题

朴素的递归斐波那契数列效率极低：

// 指数级时间复杂度 O(2^n)！
long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

问题在于大量的重复计算。fib(5) 会计算 fib(3) 两次、fib(2) 三次……随着 n 增大，重复计算呈指数增长。

3.4.2 记忆化

解决方案很简单：把算过的结果存起来：

long long memo[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // 已计算过，直接返回
    return memo[n] = fib(n - 1) + fib(n - 2);  // 计算并保存
}

int main() {
    memset(memo, -1, sizeof(memo));  // 初始化为 -1
    int n;
    scanf("%d", &n);
    printf("%lld\n", fib(n));
    return 0;
}

记忆化将时间复杂度从 O(2ⁿ) 降低到 O(n)，因为每个 fib(i) 最多只计算一次。这就是动态规划的雏形——在后续章节中，我们会将这种思想发扬光大。

三、实战案例

3.1 案例一：数字三角形

问题描述：给定一个 n 行的数字三角形，从顶部出发，每次可以走到下一行相邻的左下方或右下方的数字，求到达底部时经过数字之和的最大值。

#include <cstdio>
#include <algorithm>
using namespace std;

int a[105][105];
long long memo[105][105];
int n;

long long solve(int r, int c) {
    if (r == n - 1) return a[r][c];
    if (memo[r][c] != -1) return memo[r][c];
    return memo[r][c] = a[r][c] + max(solve(r + 1, c), solve(r + 1, c + 1));
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &a[i][j]);
    
    memset(memo, -1, sizeof(memo));
    printf("%lld\n", solve(0, 0));
    return 0;
}

解析：这是一个经典的动态规划问题。用记忆化搜索实现非常直观：solve(r, c) 表示从位置 (r, c) 到底部的最大路径和。状态转移方程为 solve(r, c) = a[r][c] + max(solve(r+1, c), solve(r+1, c+1))。

3.2 案例二：快速幂

问题描述：计算 a^b mod m，其中 a, b, m 可以达到 10⁹。

typedef long long ll;

ll power(ll a, ll b, ll m) {
    if (b == 0) return 1;
    ll half = power(a, b / 2, m);
    ll result = half * half % m;
    if (b % 2 == 1) result = result * a % m;
    return result;
}

解析：利用 a^b = (a^(b/2))² 的性质，每次将指数减半，递归深度为 O(log b)。这就是快速幂的递归实现，在数论和模运算中极为常用。

3.3 案例三：二分查找的递归实现

int binary_search(int *a, int l, int r, int target) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binary_search(a, mid + 1, r, target);
    return binary_search(a, l, mid - 1, target);
}

解析：二分查找是分治思想的直接应用——每次将搜索范围缩小一半。递归版本清晰易懂，但要注意 l + (r - l) / 2 的写法可以避免 l + r 的溢出。

四、本章小结

本章学习了函数和递归这两个核心概念：

函数是代码组织的基本单元，良好的函数设计提高代码的可读性和可复用性。

递归是函数调用自身，必须有终止条件。其执行过程对应调用栈的展开和折叠。

分治策略将大问题分解为小问题，递归求解后合并。归并排序是分治的经典应用。

记忆化搜索通过缓存结果避免重复计算，是动态规划的前身。

递归有开销：栈帧分配和函数调用都有成本，递归深度过大可能导致栈溢出。

递归不仅是一种编程技巧，更是一种思维方式。当你面对一个复杂问题时，试着问自己："这个问题能不能分解成结构相同但规模更小的子问题？"如果答案是肯定的，递归就是你的武器。

五、思考与练习

思考题

值传递和引用传递在性能上有什么区别？对于大型结构体，应该用哪种方式？

为什么全局变量在递归中可能导致问题？如何避免？

递归和循环在计算能力上是等价的吗？任何递归都能转化为迭代吗？

记忆化搜索和动态规划是什么关系？它们的区别在哪里？

编程练习

阶乘递归：用递归实现阶乘函数，并分析其时间复杂度和空间复杂度。

幂集生成：输入一个集合 {1, 2, ..., n}，用递归生成它的所有子集。

整数划分：将正整数 n 表示为若干个正整数之和，求划分方案数（用记忆化搜索）。

表达式求值：输入一个只包含加减乘除和括号的表达式，用递归方法计算其值。