L5 - 函数与递归

🎯 教学目标深化

  1. 函数设计原则
    • 单一职责原则（每个函数只做一件事）
    • 合理控制函数体长度（建议不超过50行）
    • 避免函数副作用（除非明确需要）
  2. 递归思维训练
    • 分治思想的实现方式
    • 递归树分析（用于理解递归执行路径）
    • 递归与数学归纳法的关系

🔑 核心知识点扩展

1. 函数定义深度解析

函数声明与定义的分离

1
2
3
4
5
6
7
8
9
// mymath.h（头文件）
#pragma once
int add(int a, int b); // 声明

// mymath.cpp（源文件）
#include "mymath.h"
int add(int a, int b) { // 定义
    return a + b;
}

头文件作用：

  • 提供接口文档
  • 避免重复定义
  • 支持模块化编译

默认参数机制

1
2
3
4
5
6
7
void printLog(string msg, int level=1) {
    cout << "[" << level << "] " << msg << endl;
}

// 调用示例
printLog("系统启动");     // 使用默认level=1
printLog("内存不足", 3);  // 显式指定level=3

规则说明：

  • 默认参数必须从右向左连续设置
  • 默认值在声明中指定（定义中不再重复）
  • 默认参数慎用指针和引用类型

2. 参数传递机制对比（新增指针传递）

传递方式 语法 内存操作 典型应用场景
值传递 int a 创建参数副本 基础类型小数据
引用传递 int& a 直接操作原变量 需要修改实参
指针传递 int* a 操作地址指向数据 可选参数/动态结构

指针传递示例：

1
2
3
4
5
6
7
8
9
10
11
void modifyByPointer(int* ptr, int newVal) {
    if(ptr != nullptr) { // 安全检查
        *ptr = newVal;
    }
}

int main() {
    int value = 10;
    modifyByPointer(&value, 20);
    cout << value; // 输出20
}

3. 递归算法高级应用

递归调用栈可视化

阶乘递归的栈空间变化：

1
2
3
4
5
6
| factorial(3)  | → 分配n=3
| factorial(2)  | → 分配n=2
| factorial(1)   | → 分配n=1
| return 1       | ← 释放n=1
| return 2 * 1=2   | ← 释放n=2
| return 3 * 2=6   | ← 释放n=3

尾递归优化原理

1
2
3
4
5
6
7
8
9
10
11
// 普通递归
int sum(int n) {
    if(n == 0) return 0;
    return n + sum(n-1); // 需要保存上下文
}

// 尾递归优化版
int sumTail(int n, int acc=0) {
    if(n == 0) return acc;
    return sumTail(n-1, acc+n); // 无上下文依赖
}

编译器优化效果：

  • 将尾递归转换为循环结构
  • 避免栈溢出风险
  • 时间复杂度从O(n)降为O(1)（空间复杂度）

💡 进阶技巧

1. 函数指针应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 定义函数指针类型
typedef void (*Callback)(int);

// 使用函数指针参数
void processData(int data, Callback cb) {
    // ...处理数据
    cb(result); // 回调通知
}

// 回调函数实现
void printResult(int result) {
    cout << "处理结果：" << result;
}

// 调用示例
processData(100, printResult);

2. 函数重载规则

1
2
3
4
5
6
7
8
void print(int num) { /* 处理整型 */ }
void print(double num) { /* 处理浮点型 */ }
void print(string str) { /* 处理字符串 */ }

// 调用时自动匹配最佳版本
print(10);     // 调用int版
print(3.14);   // 调用double版
print("hello");// 调用string版

重载解析规则：

  1. 精确匹配
  2. 类型提升（char→int）
  3. 标准转换（int→double）
  4. 用户定义转换

🧩 经典算法深度实现

1. 快速排序递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quickSort(int arr[], int left, int right) {
    if(left >= right) return;
    
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot-1);
    quickSort(arr, pivot+1, right);
}

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    
    for(int j=left; j<right; j++){
        if(arr[j] < pivot){
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i+1], arr[right]);
    return i+1;
}

执行过程图示：

1
2
3
原始数组：[5][3][8][6][4][7][1][2]
首趟分区：选取2为基准 → [1][3][4][5][6][8][7][2]
递归处理左右子数组

2. 二叉树遍历（先序递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void preOrder(TreeNode* root) {
    if(!root) return;
    
    cout << root->val << " "; // 访问根
    preOrder(root->left);     // 遍历左子树
    preOrder(root->right);    // 遍历右子树
}

递归树分析：

1
2
3
4
5
6
7
      1
     / \
    2   3
   / \
  4   5

遍历顺序：1 → 2 → 4 → 5 → 3

💣 易错点深度剖析

1. 栈溢出问题

错误案例：

1
2
3
4
5
int fibonacci(int n) {
    if(n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2); // 指数级递归调用
}
// 计算fib(40)将导致数百万次调用

解决方案：

  • 改用迭代法
  • 记忆化缓存（存储已计算结果）
1
2
3
4
5
6
7
8
9
10
unordered_map<int, int> cache;

int fibMemo(int n) {
    if(n <= 1) return n;
    if(cache.count(n)) return cache[n];
    
    int res = fibMemo(n-1) + fibMemo(n-2);
    cache[n] = res;
    return res;
}

2. 引用传递陷阱

未预期的修改：

1
2
3
4
5
6
7
8
void initArray(int& arr) { // 错误！数组引用语法错误
    arr = new int[10];
}

// 正确写法
void initArray(int*& arr) { // 引用传递指针
    arr = new int[10];
}

🛠️ 高级调试技巧

1. 递归调用追踪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int depth = 0; // 全局变量记录递归深度

void recursiveFunc(int n) {
    depth++;
    cout << "进入递归层数：" << depth << endl;
    
    if(n <= 0) {
        cout << "触底返回" << endl;
        depth--;
        return;
    }
    
    recursiveFunc(n-1);
    depth--;
}

// 输出示例：
// 进入递归层数：1
// 进入递归层数：2
// 触底返回

2. 内存泄漏检测

1
2
3
4
5
6
7
void testFunction() {
    int* ptr = new int[100];
    // ...未释放内存...
}

// 使用Valgrind工具检测：
// valgrind --leak-check=full ./a.out

🏋️ 配套练习升级

1. 函数性能对比器

要求：

  • 实现时间测量装饰器函数
  • 对比递归与迭代版的斐波那契计算效率
  • 输出不同规模下的耗时曲线

参考代码框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename Func>
void measureTime(Func func, string title) {
    auto start = chrono::high_resolution_clock::now();
    func();
    auto end = chrono::high_resolution_clock::now();
    cout << title << "耗时: " 
         << chrono::duration_cast<milliseconds>(end-start).count()
         << "ms" << endl;
}

// 测试用例
measureTime([]{fibRecursive(35);}, "递归版");
measureTime([]{fibIterative(35);}, "迭代版");

2. 表达式解析器

要求：

  • 实现递归下降解析器
  • 支持四则运算和括号
  • 示例输入：“3*(2+4)/2”
  • 示例输出：9