函数与递归

约 7013 字大约 23 分钟

2025-06-25

函数定义与调用、形参与实参

函数

在C++中，函数是封装特定功能的代码块，通过函数可以实现代码复用和逻辑模块化，是信奥赛中组织程序结构的核心工具。

一、函数的基本概念

函数的基本概念

函数是完成特定任务的代码单元，包含函数定义（实现功能）和函数调用（使用功能）两个核心环节。

1. 函数的作用

代码复用：避免重复编写相同逻辑（如多次使用的排序、计算功能）。
模块化：将复杂问题拆分为多个函数，使程序结构清晰（如信奥赛中的“读入数据”“处理逻辑”“输出结果”可分函数实现）。
抽象逻辑：隐藏实现细节，只需关注“输入什么”和“输出什么”。

二、函数定义

函数定义

函数定义描述函数的功能实现，包含返回值类型、函数名、形参列表和函数体。

1. 语法格式

c++

返回值类型 函数名(参数列表) {
    // 函数体：实现功能的语句
    return 返回值;  // 与返回值类型匹配
}

2. 各部分说明

返回值类型：函数执行后返回的数据类型（如int、double）；无返回值时用void。
函数名：标识符，遵循变量命名规则（见名知意，如max、calcSum）。
参数列表：用逗号分隔的形参（形式参数），格式为“类型形参名”；无参数时可留空或写void。
函数体：包含实现功能的语句，用{}包裹。
return语句：结束函数并返回结果（void类型函数可省略return）。

3. 示例

c++

// 定义一个求两数之和的函数
int add(int a, int b) {  // int：返回值类型；add：函数名；a,b：形参
    int sum = a + b;
    return sum;  // 返回计算结果
}

// 定义一个无返回值、无参数的函数
void printHello() {
    cout << "Hello, World!" << endl;
    // 无return语句
}

三、函数调用

函数调用

函数调用是使用已定义函数的过程，通过函数名触发函数体执行，并传入实际数据。

1. 语法格式

c++

函数名(实参列表);  // 无返回值时
返回值类型 变量 = 函数名(实参列表);  // 有返回值时，用变量接收

2. 示例

c++

#include <iostream>
using namespace std;

// 先定义函数（或声明）
int add(int a, int b) { return a + b; }
void printHello() { cout << "Hello!" << endl; }

int main() {
    // 调用无返回值函数
    printHello();  // 输出"Hello!"

    // 调用有返回值函数，传入实参并接收结果
    int x = 3, y = 5;
    int result = add(x, y);  // x,y是实参，result接收返回值5+3=8
    cout << result << endl;  // 输出8

    // 直接使用返回值（不存储）
    cout << add(10, 20) << endl;  // 输出30

    return 0;
}

四、形参和实参（核心区别）

形参和实参

1. 形参（形式参数）

位置：函数定义的参数列表中。
作用：声明函数需要接收的数据类型和名称，相当于函数内部的局部变量。
生命周期：仅在函数被调用时创建，函数执行结束后销毁。
示例：add(int a, int b)中的a和b。

2. 实参（实际参数）

位置：函数调用时传入的参数。
作用：提供函数执行所需的具体数据，可是常量、变量、表达式等。
要求：实参类型必须与形参类型兼容（可自动转换，如int→double），数量必须与形参一致。
示例：add(x, y)中的x和y，add(10, 20)中的10和20。

3. 传递规则

函数调用时，实参的值会复制给形参（值传递），形参的修改不影响实参。

c++

void swap(int a, int b) {  // a,b是形参
    int temp = a;
    a = b;
    b = temp;  // 仅交换形参的值
}

int main() {
    int x = 3, y = 5;
    swap(x, y);  // x,y是实参
    cout << x << " " << y;  // 输出3 5（实参未被修改）
    return 0;
}

五、函数声明（原型）

函数声明

当函数定义在调用之后时，需提前声明函数原型，告诉编译器函数的存在。

1. 语法格式

c++

返回值类型 函数名(参数列表);  // 与定义的首部一致，末尾加;

2. 示例

c++

#include <iostream>
using namespace std;

// 函数声明（原型）：告诉编译器有一个这样的函数
int add(int a, int b);  // 无需函数体，参数名可省略（如int add(int, int);）
void printHello();

int main() {
    // 调用声明过的函数（此时函数尚未定义，仍可调用）
    cout << add(3, 5) << endl;
    printHello();
    return 0;
}

// 函数定义（需与声明一致）
int add(int a, int b) {
    return a + b;
}

void printHello() {
    cout << "Hello!" << endl;
}

六、信奥赛常见函数类型

信奥赛常见函数类型

1. 有返回值、有参数（最常用）

c++

// 求最大值
int max(int a, int b) {
    return a > b ? a : b;
}

2. 有返回值、无参数

c++

// 生成随机数（1~100）
int getRandom() {
    return rand() % 100 + 1;
}

3. 无返回值、有参数

c++

// 输出数组元素
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

4. 无返回值、无参数

c++

// 输出分隔线
void printLine() {
    cout << "-----------------" << endl;
}

七、避坑指南

避坑指南

函数未声明或定义：调用前必须声明或定义函数，否则编译器会报错“未声明的标识符”。
形参与实参不匹配：数量、类型必须一致（或可转换），否则会编译错误：

c++

add(3.5, 5);  // 错误：形参是int，实参是double（部分编译器允许，但不推荐）
add(1, 2, 3); // 错误：实参数量多于形参

返回值类型不匹配：return语句的返回值类型必须与函数声明的返回值类型一致：

c++

int func() {
    return 3.5;  // 错误：返回double，函数声明为int
}

值传递的局限性：形参修改不影响实参，若需修改实参，需用指针或引用（信奥赛进阶内容）。
函数嵌套定义：C++不允许函数内部定义另一个函数（嵌套定义），需在外部定义后调用。

八、实战：用函数实现数组求和与平均值

数组求和与平均值

c++

#include <iostream>
using namespace std;

// 声明函数
int sumArray(int arr[], int n);  // 求数组和
double avgArray(int arr[], int n);  // 求平均值

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;

    int s = sumArray(arr, n);
    double a = avgArray(arr, n);

    cout << "数组和：" << s << endl;    // 输出15
    cout << "平均值：" << a << endl;  // 输出3

    return 0;
}

// 定义求和函数
int sumArray(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

// 定义求平均值函数（复用求和函数）
double avgArray(int arr[], int n) {
    if (n == 0) return 0;  // 避免除以0
    return (double)sumArray(arr, n) / n;  // 调用sumArray
}

重要

函数是信奥赛中程序设计的基础，通过函数封装可使代码结构清晰、易于维护。掌握函数的定义、调用、形参与实参的区别，以及函数声明的用法，是编写复杂程序的前提。在实际解题中，合理拆分功能为函数，能显著提高代码效率和可读性。

传值参数与传引用参数

在C++中，函数参数的传递方式有两种：传值参数（值传递）和传引用参数（引用传递）。两者的核心区别在于是否会复制参数值，以及是否能修改原始变量，这在信奥赛中对程序逻辑和效率有重要影响。

一、传值参数（值传递）

传值参数（值传递）

传值参数是默认的参数传递方式，函数接收的是实参的副本（复制值），对形参的修改不会影响实参。

1. 原理与示例

c++

#include <iostream>
using namespace std;

// 传值参数：形参a是实参的副本
void increment(int a) {
    a++;  // 仅修改副本
    cout << "函数内：" << a << endl;  // 输出6
}

int main() {
    int x = 5;
    increment(x);  // 传入x的值（复制给a）
    cout << "函数外：" << x << endl;  // 输出5（x未被修改）
    return 0;
}

2. 特点

安全性：实参被保护，函数内的操作不会影响外部变量。
开销：传递大对象（如大型数组、结构体）时，复制操作会消耗内存和时间（效率低）。
适用场景：只需使用参数值，无需修改原始变量（如计算、判断）。

二、传引用参数（引用传递）

传引用参数（引用传递）

传引用参数通过引用（&） 接收实参，函数直接操作原始变量，对形参的修改会同步影响实参。

1. 原理与示例

c++

#include <iostream>
using namespace std;

// 传引用参数：形参a是x的引用（别名）
void increment(int& a) {  // &表示引用
    a++;  // 直接修改原始变量x
    cout << "函数内：" << a << endl;  // 输出6
}

int main() {
    int x = 5;
    increment(x);  // 传入x的引用（不复制）
    cout << "函数外：" << x << endl;  // 输出6（x被修改）
    return 0;
}

2. 特点

修改性：可直接修改实参，适合需要“返回多个结果”的场景（无需用指针）。
效率：无需复制参数，传递大对象时效率极高（仅传递地址）。
语法：形参声明时加&（如int& a），调用时直接传变量名（与传值调用语法相同）。
风险：若误修改引用参数，会影响原始变量，需谨慎操作。

三、核心区别对比

特性	传值参数（`int a`）	传引用参数（`int& a`）
实参是否被修改	不会（操作副本）	会（操作原始变量）
参数传递开销	复制值（大对象开销大）	无复制（仅传递引用，开销极小）
适用场景	只读参数（如计算、输出）	需要修改实参（如交换、累加、多返回值）
形参本质	实参的副本（独立变量）	实参的别名（与实参同内存）

四、信奥赛典型应用

典型应用

1. 传值参数：只读操作

c++

// 计算两数之和（仅使用参数值，不修改）
int add(int a, int b) {  // 传值，安全
    return a + b;
}

2. 传引用参数：修改实参

交换两个变量：

c++

// 传引用实现交换（直接修改实参）
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 调用：
int x = 3, y = 5;
swap(x, y);  // x=5, y=3（成功交换）

返回多个结果：函数只能有一个返回值，通过引用参数可“输出”多个结果：

c++

// 计算数组的最大值和最小值（通过引用返回）
void getMaxMin(int arr[], int n, int& maxVal, int& minVal) {
    maxVal = arr[0];
    minVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
        if (arr[i] < minVal) minVal = arr[i];
    }
}

// 调用：
int arr[] = {1,3,5,2,4};
int max, min;
getMaxMin(arr, 5, max, min);  // max=5, min=1（通过引用获取结果）

3. 常量引用（`const &`）：高效只读

对于大对象（如字符串、结构体），既想避免复制开销，又不想被修改，可用常量引用：

c++

// 输出字符串（只读，用const&避免复制）
void printString(const string& s) {  // const确保s不被修改
    cout << s << endl;
    // s += "x";  // 错误：常量引用不可修改
}

五、避坑指南

避坑指南

引用参数必须初始化：
引用本质是别名，必须绑定到一个已存在的变量，不能传递常量或表达式：

c++

void func(int& a) { ... }
func(5);  // 错误：不能将引用绑定到常量
func(x + 3);  // 错误：不能绑定到表达式

传值与传引用的调用语法相同：
调用时仅看函数定义，与传值调用写法一致，需注意函数参数是否为引用：

c++

void f1(int a) { ... }  // 传值
void f2(int& a) { ... } // 传引用

int x = 5;
f1(x);  // 传值，x不变
f2(x);  // 传引用，x可能被修改

数组的特殊处理：
数组作为参数时，看似传值，实际是传指针（类似引用效果），修改数组元素会影响实参：
c++
```
void modifyArray(int arr[], int n) {
    arr[0] = 100;  // 会修改实参数组
}
```

六、实战：用引用参数优化数组操作

引用参数优化数组操作

题目：编写函数，同时计算数组的和、平均值、最大值（通过引用参数返回多个结果）。

c++

#include <iostream>
using namespace std;

// 计算数组的和、平均值、最大值（通过引用返回后三者）
void calcArray(int arr[], int n, int& sum, double& avg, int& maxVal) {
    sum = 0;
    maxVal = arr[0];
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    avg = (n == 0) ? 0 : (double)sum / n;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = 5;
    int sum, maxVal;
    double avg;

    // 调用函数，通过引用获取多个结果
    calcArray(arr, n, sum, avg, maxVal);

    cout << "和：" << sum << endl;    // 30
    cout << "平均值：" << avg << endl;  // 6
    cout << "最大值：" << maxVal << endl;  // 10

    return 0;
}

重要

传值参数和传引用参数是C++函数设计的核心技巧。信奥赛中，传值适合简单只读场景，传引用适合需要修改实参或传递大对象的场景，而常量引用则兼顾效率和安全性。掌握两者的区别和适用场景，能显著提升代码的效率和逻辑清晰度。

常量与变量的作用范围

在C++中，常量与变量的作用范围（作用域） 指的是它们能被访问的代码区域。理解作用域是避免命名冲突、合理组织代码的关键，在信奥赛中尤其直接影响程序的正确性。

一、作用域的基本规则

作用域的基本规则

作用域由代码块（{} 包裹的区域）决定，遵循**“就近原则”**：

变量/常量在声明的代码块内可见（可访问）。
离开声明的代码块后，变量/常量自动销毁（局部变量）或不可访问。

二、变量的作用范围（按声明位置分类）

变量的作用范围（按声明位置分类）

1. 局部变量（块作用域）

声明位置：函数内部、循环/分支语句的代码块中（{} 内）。
作用范围：从声明位置到所在代码块结束（}）。
生命周期：进入代码块时创建，离开代码块时销毁（仅在作用域内有效）。

示例：

c++

#include <iostream>
using namespace std;

int main() {
    int a = 10;  // 局部变量，作用域从声明到main函数结束
    
    if (a > 5) {
        int b = 20;  // 局部变量，作用域仅限if的{}内
        cout << a + b << endl;  // 正确：a和b均在作用域内
    }
    
    // cout << b << endl;  // 错误：b的作用域已结束（离开if的{}）
    return 0;
}

信奥赛注意：循环内部声明的变量，每次循环都会重新创建和销毁：

c++

for (int i = 0; i < 3; i++) {  // i的作用域仅限for循环内
    int j = i * 2;  // j每次循环都重新声明
}
// cout << i << j;  // 错误：i和j已超出作用域

2. 全局变量（文件作用域）

声明位置：所有函数外部（通常在文件开头）。
作用范围：从声明位置到整个文件结束，所有函数均可访问。
生命周期：程序启动时创建，程序结束时销毁（全程有效）。

示例：

c++

#include <iostream>
using namespace std;

int g_var = 100;  // 全局变量，作用域覆盖整个文件

void func() {
    cout << "函数内访问全局变量：" << g_var << endl;  // 正确
}

int main() {
    cout << "main内访问全局变量：" << g_var << endl;  // 正确
    func();
    return 0;
}

信奥赛注意：

全局变量默认初始化为0（局部变量不初始化则为随机值）。
应尽量避免使用全局变量：易引发命名冲突，且函数依赖全局变量会降低复用性。

3. 函数参数（函数作用域）

声明位置：函数定义的参数列表中。
作用范围：整个函数体内部（与函数内的局部变量同级）。
本质：属于函数的局部变量，随函数调用创建，调用结束销毁。

示例：

c++

void func(int x) {  // x是函数参数，作用域为整个func函数体
    cout << x << endl;  // 正确
}

int main() {
    // cout << x << endl;  // 错误：x的作用域仅限func内
    return 0;
}

三、常量的作用范围

常量的作用范围

常量（const 修饰）的作用域规则与变量一致，但根据声明位置也分为：

1. 局部常量（块作用域）

c++

int main() {
    const int MAX = 100;  // 局部常量，作用域仅限main内
    if (true) {
        const int MIN = 0;  // 作用域仅限if的{}内
    }
    // cout << MIN << endl;  // 错误：MIN已出作用域
    return 0;
}

2. 全局常量（文件作用域）

c++

const double PI = 3.14159;  // 全局常量，整个文件可访问

void calcArea(double r) {
    double area = PI * r * r;  // 正确使用全局常量
}

四、作用域的核心冲突与解决

作用域的核心冲突与解决

1. 同名变量的“就近覆盖”

当局部变量与全局变量同名时，局部变量优先（覆盖全局变量）：

c++

int a = 10;  // 全局变量

int main() {
    int a = 20;  // 局部变量，与全局变量同名
    cout << a << endl;  // 输出20（局部变量优先）
    return 0;
}

访问被覆盖的全局变量：用 ::（作用域解析符）：

c++

int a = 10;

int main() {
    int a = 20;
    cout << a << endl;       // 20（局部）
    cout << ::a << endl;     // 10（全局）
    return 0;
}

2. 嵌套块的作用域

内层代码块的变量会覆盖外层同名变量：

c++

int main() {
    int x = 5;
    {
        int x = 10;  // 内层变量，覆盖外层x
        cout << x << endl;  // 输出10
    }
    cout << x << endl;  // 输出5（外层x）
    return 0;
}

五、信奥赛避坑指南

避坑指南

避免全局变量滥用：
全局变量在所有函数中可见，修改后可能引发连锁错误（尤其多人协作或复杂程序）。信奥赛中建议用函数参数传递数据，而非依赖全局变量。

局部变量必须初始化：
局部变量未初始化时，值为随机垃圾值，可能导致计算错误：

c++

int main() {
    int x;
    // cout << x << endl;  // 错误：x未初始化，值不确定
    int y = 0;  // 正确：显式初始化
    return 0;
}

注意循环变量的作用域：
C++11后，for循环的变量可声明在循环内（作用域仅限循环），避免污染外部：
c++
```
for (int i = 0; i < 5; i++) { ... }
// cout << i;  // 错误：i的作用域仅限循环内
```
常量用const而非#define：
#define 是预处理指令，无作用域限制，可能引发意外替换；const 常量有明确作用域，更安全：
c++
```
#define MAX 100  // 无作用域，整个文件有效（甚至其他文件）
const int MAX = 100;  // 有作用域，更可控
```

六、实战：作用域综合应用

作用域综合应用

c++

#include <iostream>
using namespace std;

int global = 10;  // 全局变量

void func() {
    int local = 20;  // 局部变量
    cout << "func内：global=" << global << ", local=" << local << endl;
}

int main() {
    int local = 30;  // 局部变量（覆盖可能的同名全局变量）
    const int CONST_VAL = 100;  // 局部常量

    cout << "main内：global=" << global << ", local=" << local << endl;
    func();

    if (true) {
        int local = 40;  // 内层局部变量（覆盖main的local）
        cout << "if内：local=" << local << ", CONST_VAL=" << CONST_VAL << endl;
    }

    // cout << "if外访问内层local：" << local << endl;  // 错误：内层local已销毁
    return 0;
}

console

main内：global=10, local=30
func内：global=10, local=20
if内：local=40, CONST_VAL=100

重要

常量与变量的作用域是C++程序设计的基础概念。信奥赛中，合理控制作用域可避免命名冲突、减少bug，尤其要注意局部变量的初始化和全局变量的慎用。掌握“就近原则”和作用域的嵌套规则，能写出更清晰、安全的代码。

递归函数

在C++中，递归函数是指在函数体内直接或间接调用自身的函数。它通过将复杂问题分解为与原问题结构相似的子问题，逐步简化问题规模，最终通过解决最小子问题（基线条件）反推原问题的解。递归在信奥赛中广泛应用于深度优先搜索（DFS）、分治算法、树形结构遍历等场景。

一、递归的核心要素

递归的核心要素

递归函数必须满足两个关键条件，否则会陷入无限循环（导致栈溢出）：

基线条件（终止条件）：
当问题规模缩小到可直接求解的程度时，不再调用自身，直接返回结果。这是递归的“出口”。
递归条件：
将原问题分解为规模更小的子问题，通过调用自身解决子问题，再用子问题的结果构建原问题的解。

二、递归函数的基本示例

递归函数的基本示例

1. 计算阶乘（n!）

阶乘的数学定义：

n! = n × (n-1) × (n-2) × ... × 1
0! = 1（基线条件）

递归实现：

c++

#include <iostream>
using namespace std;

// 递归计算n的阶乘
int factorial(int n) {
    // 基线条件：n=0时返回1
    if (n == 0) {
        return 1;
    }
    // 递归条件：n! = n × (n-1)!
    return n * factorial(n - 1);
}

int main() {
    int n = 5;
    cout << n << "! = " << factorial(n) << endl;  // 输出120
    return 0;
}

console

factorial(5) → 5 × factorial(4)  
factorial(4) → 4 × factorial(3)  
factorial(3) → 3 × factorial(2)  
factorial(2) → 2 × factorial(1)  
factorial(1) → 1 × factorial(0)  
factorial(0) → 1（基线条件）  
// 逐层返回计算结果：1×1=1 → 2×1=2 → 3×2=6 → 4×6=24 → 5×24=120

2. 斐波那契数列（第n项）

斐波那契数列定义：

F(0) = 0，F(1) = 1（基线条件）
F(n) = F(n-1) + F(n-2)（n ≥ 2，递归条件）

递归实现：

c++

int fibonacci(int n) {
    // 基线条件
    if (n == 0) return 0;
    if (n == 1) return 1;
    // 递归条件
    return fibonacci(n - 1) + fibonacci(n - 2);
}

三、递归的执行原理（调用栈）

递归的执行原理（调用栈）

递归函数的每次调用都会在内存的调用栈中创建一个新的“栈帧”，存储当前函数的参数、局部变量和返回地址。当达到基线条件后，栈帧会逐层弹出，将结果返回给上一层调用。

示例：factorial(3)的调用栈变化

console

调用 factorial(3) → 栈帧1：n=3  
  调用 factorial(2) → 栈帧2：n=2  
    调用 factorial(1) → 栈帧3：n=1  
      调用 factorial(0) → 栈帧4：n=0（基线条件，返回1）  
    栈帧3返回：1×1=1  
  栈帧2返回：2×1=2  
栈帧1返回：3×2=6

注意：调用栈的深度有限（通常为几千层），若递归深度过深（如n=1e5），会导致栈溢出（程序崩溃）。

四、信奥赛中的递归应用

信奥赛中的递归应用

1. 深度优先搜索（DFS）

遍历图或树时，递归是最自然的实现方式：

c++

// 递归遍历数组的所有元素（模拟DFS）
void dfs(int arr[], int index, int n) {
    if (index == n) {  // 基线条件：遍历完所有元素
        return;
    }
    cout << arr[index] << " ";  // 访问当前元素
    dfs(arr, index + 1, n);  // 递归遍历下一个元素
}

2. 分治算法（如归并排序）

将数组分为两半，递归排序每一半，再合并：

c++

void mergeSort(int arr[], int left, int right) {
    if (left >= right) {  // 基线条件：子数组长度为1（已排序）
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);    // 递归排序左半
    mergeSort(arr, mid + 1, right);  // 递归排序右半
    merge(arr, left, mid, right);  // 合并两个有序子数组
}

3. 汉诺塔问题

经典递归问题：将n个盘子从A柱移到C柱，中间可借助B柱，每次只能移一个盘子且大盘不能压小盘。

c++

// 将n个盘子从from柱移到to柱，借助aux柱
void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {  // 基线条件：1个盘子直接移
        cout << "移动盘子1从" << from << "到" << to << endl;
        return;
    }
    // 步骤1：将n-1个盘子从from移到aux（借助to）
    hanoi(n - 1, from, to, aux);
    // 步骤2：将第n个盘子从from移到to
    cout << "移动盘子" << n << "从" << from << "到" << to << endl;
    // 步骤3：将n-1个盘子从aux移到to（借助from）
    hanoi(n - 1, aux, from, to);
}

五、递归的优缺点与优化

递归的优缺点与优化

1. 优点

代码简洁：直接反映问题的递归定义（如数学公式、分治逻辑）。
逻辑清晰：避免手动管理循环和栈，适合树形、嵌套结构问题。

2. 缺点

效率问题：重复计算（如斐波那契数列的递归实现会多次计算同一子问题）。
栈溢出风险：递归深度过深时，调用栈会耗尽内存。

3. 优化技巧

记忆化递归：用数组或哈希表存储已计算的子问题结果，避免重复计算：

c++

// 记忆化优化斐波那契数列
int memo[100] = {0};  // 存储已计算的结果
int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n];  // 直接返回已计算的结果
    memo[n] = fib(n - 1) + fib(n - 2);  // 存储计算结果
    return memo[n];
}

递归转迭代：对于深度过深的问题，用循环和手动栈模拟递归（避免栈溢出）。

六、避坑指南

避坑指南

必须有明确的基线条件：
遗漏基线条件会导致无限递归，最终栈溢出（程序崩溃）：

c++

// 错误示例：无基线条件
int func(int n) {
    return func(n - 1);  // 无限调用，最终崩溃
}

控制递归深度：
信奥赛中若n超过1e4，递归可能栈溢出，需改用迭代或优化：

c++

// 阶乘的迭代实现（适合大n）
int factorialIter(int n) {
    int res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

避免重复计算：
如未优化的斐波那契递归，时间复杂度为O(2ⁿ)，n=30就会有百万次计算，必须用记忆化优化。

七、实战：递归计算数组元素和

递归计算数组元素和

题目：用递归求数组前n个元素的和。

c++

#include <iostream>
using namespace std;

// 递归计算arr[0..n-1]的和
int sumArray(int arr[], int n) {
    if (n == 0) {  // 基线条件：空数组和为0
        return 0;
    }
    // 递归条件：前n个元素和 = 第n-1个元素 + 前n-1个元素和
    return arr[n - 1] + sumArray(arr, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    cout << "数组和：" << sumArray(arr, n) << endl;  // 输出15
    return 0;
}

重要

递归是信奥赛中解决复杂问题的强大工具，其核心是“分解问题+基线条件”。掌握递归的思想，能高效解决DFS、分治、树形结构等问题，但需注意优化重复计算和控制递归深度，避免常见陷阱。在实际解题中，需根据问题特点选择递归或迭代，平衡代码简洁性和效率。

基础知识与编程环境

C++程序设计

数据结构

算法

数学与其他

基础知识与编程环境

C++程序设计

函数与递归