L8.2 - 递归&指针深度解析（拓展）

🎯 教学目标

  1. 掌握递归核心原理：理解调用栈机制与递归三要素
  2. 精通指针操作技巧：从内存层面理解程序运行机制
  3. 规避递归与指针陷阱：识别常见错误模式
  4. 开发复杂数据结构：实现链表、树等递归结构

📚 核心知识点

一、递归核心原理

1. 递归三要素

1
2
3
4
5
6
7
8
9
10
int factorial(int n) {
    // 终止条件
    if(n == 0) return 1;          // 要素1：基准情形
    
    // 递归调用
    int prev = factorial(n-1);   // 要素2：递归推进
    
    // 状态合并
    return n * prev;             // 要素3：问题分解
}

二、指针操作全景

1. 指针类型体系

类型 示例 内存示意图
裸指针 int* p = &a; [a地址] → 42
双指针 int** pp = &p; [pp地址] → [p地址] → 42
函数指针 void (*fp)(int); 指向函数入口地址
智能指针 unique_ptr<int> up; 自动管理生命周期

2. 指针运算本质

1
2
3
4
5
int arr[5] = {10,20,30,40,50};
int* p = arr;         // p → arr[0]

p += 3;               // p → arr[3]
int diff = p - arr;   // diff = 3 (元素个数差)

💡 实战应用场景

1. 递归链表处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// 递归反转链表
Node* reverseList(Node* head) {
    if(!head || !head->next) return head;
    Node* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

2. 多级指针应用

1
2
3
4
5
6
7
8
9
10
void allocateMatrix(int*** matrix, int rows, int cols) {
    *matrix = new int*[rows];
    for(int i=0; i<rows; ++i){
        (*matrix)[i] = new int[cols];
    }
}

// 调用示例
int** mat = nullptr;
allocateMatrix(&mat, 5, 5);

💣 深度陷阱解析

1. 递归栈溢出

1
2
3
4
5
6
7
8
9
10
// 危险代码：无终止条件的递归
void infiniteRecur() {
    infiniteRecur();  // 最终导致Stack Overflow
}

// 正确模式：确保递归深度可控
void safeRecur(int depth) {
    if(depth > 1000) return;  // 深度限制
    safeRecur(depth+1);
}

2. 指针悬挂引用

1
2
3
4
5
6
7
8
9
int* dangerPointer() {
    int local = 42;
    return &local;  // 返回局部变量地址 → 未定义行为
}

// 正确做法：动态内存分配
int* safePointer() {
    return new int(42);  // 需配合delete使用
}

🧩 进阶训练系统

1. 递归分形生成

1
2
3
4
5
6
7
8
9
10
void drawTree(Point start, double angle, int depth) {
    if(depth == 0) return;
    
    Point end = calculateEndPoint(start, angle);
    drawLine(start, end);
    
    // 递归生成子树
    drawTree(end, angle-20, depth-1);  // 左分支
    drawTree(end, angle+20, depth-1);  // 右分支
}

2. 智能指针实践

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode {
public:
    int value;
    shared_ptr<TreeNode> left;
    shared_ptr<TreeNode> right;
    
    TreeNode(int val) : value(val) {}
};

// 创建树结构
auto root = make_shared<TreeNode>(1);
root->left = make_shared<TreeNode>(2);
root->right = make_shared<TreeNode>(3);

🔍 调试技巧宝典

1. 递归调用追踪

1
2
3
4
5
6
7
8
9
10
11
12
void recurDebug(int n, int depth=0) {
    cout << string(depth, ' ') << "Enter: n=" << n << endl;
    if(n <= 0) {
        cout << string(depth, ' ') << "Base case" << endl;
        return;
    }
    recurDebug(n-1, depth+2);
    cout << string(depth, ' ') << "Exit: n=" << n << endl;
}

// 调用示例
recurDebug(3);

2. 指针有效性检测

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename T>
void safeDelete(T*& ptr) {
    static_assert(!is_array<T>::value, 
        "Use safeDeleteArray for arrays");
    if(ptr) {
        delete ptr;
        ptr = nullptr;  // 防止悬垂指针
    }
}

// 使用示例
int* p = new int(10);
safeDelete(p);

📊 性能优化指南

1. 尾递归优化

1
2
3
4
5
6
7
8
9
// 传统递归
int factorial(int n) {
    return (n <= 1) ? 1 : n * factorial(n-1);
}

// 尾递归优化版
int tailFact(int n, int acc = 1) {
    return (n <= 1) ? acc : tailFact(n-1, n*acc);
}

2. 指针别名优化

1
2
3
4
5
6
void processData(int* a, int* b, int size) {
    // 使用__restrict关键字避免指针别名
    for(int i=0; i<size; ++i) {
        a[i] = b[i] * 2;  // 编译器可做向量化优化
    }
}

🛠️ 拓展模块：逆向工程基础

1. 函数指针实战

1
2
3
4
5
6
7
8
9
10
11
12
13
// 回调函数示例
void eventHandler(int code, void (*callback)(int)) {
    cout << "Processing event: " << code << endl;
    callback(code * 100);
}

// 注册回调
void myCallback(int data) {
    cout << "Received: " << data << endl;
}

// 调用示例
eventHandler(5, myCallback);

2. 内存布局分析

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Complex {
    double real;
    double imag;
    void print() { 
        cout << real << "+" << imag << "i" << endl; 
    }
};

// 通过指针修改对象内存
Complex c{1.0, 2.0};
double* p = reinterpret_cast<double*>(&c);
p[1] = 3.14;  // 修改imag成员
c.print();     // 输出1+3.14i