1.C++递归函数

1.1 递归的本质：自己调用自己

       递归，简单来说就是函数在执行过程中直接或间接地调用自身的编程技巧。它的思想源于数学中的递归定义，比如我们熟悉的阶乘：

       n!={1n×(n−1)!​(n=0)(n>0)​

 这个定义完美体现了递归的核心：终止条件（n=0时返回 1）和递归关系（n! = n × (n-1)!）。

1.2 C++ 中递归的两种形式

       在 C++ 中，递归分为直接递归和间接递归两种形式。

       1.2.1  直接递归：函数自己调用自己

       直接递归是最直观的递归形式，函数在执行过程中直接调用自身。我们以阶乘计算为例，实现一个直接递归函数：

#include <iostream>
using namespace std;

// 计算n的阶乘的递归函数
long long factorial(int n) {
    // 终止条件：n=0时返回1
    if (n == 0) {
        return 1;
    } else {
        // 递归关系：n! = n × (n-1)!
        return n * factorial(n - 1);
    }
}

int main() {
    int n;
    cout << "请输入一个非负整数：";
    cin >> n;
    cout << n << "的阶乘是：" << factorial(n) << endl;
    return 0;
}

       在这个例子中，factorial函数在n > 0时调用了自身（factorial(n - 1)），直到触发终止条件n == 0才开始回溯计算，最终得到结果。

       1.2.2 间接递归：函数通过其他函数调用自身

       间接递归是指函数 A 调用函数 B，函数 B 又调用函数 A（或经过多个函数调用后回到 A）的情况。我们通过一个 “奇数 / 偶数判断” 的例子来理解：

#include <iostream>
using namespace std;

// 判断是否为偶数
bool isEven(int n);

// 判断是否为奇数
bool isOdd(int n) {
    // 终止条件：n=0时不是奇数
    if (n == 0) {
        return false;
    } else {
        // 间接递归：奇数 = 不是偶数
        return !isEven(n - 1);
    }
}

bool isEven(int n) {
    // 终止条件：n=0时是偶数
    if (n == 0) {
        return true;
    } else {
        // 间接递归：偶数 = 不是奇数
        return !isOdd(n - 1);
    }
}

int main() {
    int num;
    cout << "请输入一个整数：";
    cin >> num;
    if (isEven(num)) {
        cout << num << "是偶数" << endl;
    } else {
        cout << num << "是奇数" << endl;
    }
    return 0;
}

          在这个例子中，isOdd调用了isEven，isEven又调用了isOdd，形成了间接递归。

1.3 递归函数的设计方法

     设计一个健壮的递归函数，通常遵循以下步骤：

1. 确定终止条件：明确递归何时停止，避免无限递归。
2. 推导递归关系：找到问题的大实例与小实例之间的联系。

3. 斐波那契数列的定义为：

   F(n)=⎩⎨⎧​01F(n−1)+F(n−2)​(n=0)(n=1)(n>1)​

   对应的 C++ 递归实现：

#include <iostream>
using namespace std;

// 计算斐波那契数列的第n项
long long fibonacci(int n) {
    // 终止条件
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        // 递归关系
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int n;
    cout << "请输入项数n：";
    cin >> n;
    cout << "斐波那契数列第" << n << "项是：" << fibonacci(n) << endl;
    return 0;
}

1.4 递归的优缺点与适用场景

优点：

• 代码简洁优雅，符合人类的思维逻辑，尤其是处理树形结构（如二叉树遍历）、分治问题（如快速排序、归并排序）时，递归的表达力极强。

缺点：

• 可能存在栈溢出风险（当递归深度过大时，函数调用栈被耗尽）。
• 重复计算问题（如斐波那契数列的递归实现，存在大量重复计算），可以通过记忆化搜索优化。

适用场景：

• 问题可以被分解为结构相同的子问题（如阶乘、斐波那契数列）。
• 处理具有递归结构的数据（如链表、树、图的遍历）。
• 实现分治算法（如快速排序、汉诺塔问题）。

1.5 总结

       递归是 C++ 中强大的编程工具，它以 “自我调用” 的形式将复杂问题拆解为简单子问题。掌握递归的关键在于理解终止条件和递归关系，同时也要注意其潜在的栈溢出和重复计算问题。

2. C++指针部分

2.1 指针的本质：内存地址的 “容器”

       在计算机内存中，每个存储单元都有唯一的编号，这就是地址。指针变量的本质就是用来存储这些地址的变量，它能让我们直接操控内存中的数据。

       可以把内存想象成一条街道，每个存储单元是 “房子”，地址是 “门牌号”，而指针就是 “记录门牌号的小本子”。

2.2 指针变量的定义

定义指针变量的格式为：数据类型 * 变量名;

• 数据类型：指针指向的变量的数据类型（可以是基本类型、构造类型甚至void类型）。
• *：表示这是一个指针变量，而非普通变量。
• 变量名：用户自定义的标识符。

代码示例：不同类型指针的定义

#include <iostream>
using namespace std;

int main() {
    // 定义int型指针ip，用于存储int变量的地址
    int *ip;
    // 定义float型指针fp，用于存储float变量的地址
    float *fp;
    
    // 用typedef自定义数组类型后定义指针
    typedef int A[10];
    A *ap;
    
    cout << "int*指针大小：" << sizeof(ip) << endl;
    cout << "float*指针大小：" << sizeof(fp) << endl;
    cout << "自定义类型指针大小：" << sizeof(ap) << endl;
    
    return 0;
}

输出说明：在大多数环境中，上述三种指针的大小都会输出4（或8，取决于系统位数）。这是因为指针存储的是内存地址，其大小由系统的寻址能力决定，与指向的变量类型无关。

2.3 指针的核心操作：取地址与解引用

指针的使用主要围绕两个操作：取地址（&）和解引用（*）。

1. 取地址操作（&）

用于获取变量的内存地址，格式为&变量名。

2. 解引用操作（*）

通过指针存储的地址，访问对应的内存数据，格式为*指针变量名。

代码示例：指针的基本操作

#include <iostream>
using namespace std;

int main() {
    int num = 100;
    // 定义int型指针ip，并存储num的地址
    int *ip = &num;
    
    cout << "num的地址：" << &num << endl;
    cout << "指针ip存储的地址：" << ip << endl;
    cout << "通过指针ip访问num的值：" << *ip << endl;
    
    // 通过指针修改num的值
    *ip = 200;
    cout << "修改后num的值：" << num << endl;
    
    return 0;
}

输出结果：

num的地址：0x7ffeefbff5ec
指针ip存储的地址：0x7ffeefbff5ec
通过指针ip访问num的值：100
修改后num的值：200

       从结果可以看到，指针ip存储了num的地址，通过解引用操作*ip可以直接读写num的内容，这就是指针操作内存的核心逻辑。

2.4 指针的应用场景与注意事项

1. 典型应用场景

• 函数传址调用：实现函数对变量的 “双向” 修改（如交换两个变量的值）。
• 动态内存分配：配合new和delete操作符，在堆区灵活管理内存。
• 操作数组与字符串：数组名本质是指针，指针可高效遍历数组元素。
• 数据结构实现：链表、树、图等结构的节点连接，依赖指针实现。

2. 注意事项

• 空指针：定义指针时若暂时无地址可指，可初始化为nullptr（C++11 特性），避免野指针。
• 野指针：指针指向的内存已释放或未合法分配，操作野指针会导致程序崩溃。
• 指针类型匹配：尽量保证指针类型与指向变量的类型一致，避免类型不匹配导致的未定义行为。

2.5 总结

       指针是 C++ 直接操作内存的 “利器”，它通过存储地址实现了对变量的灵活控制。从定义（数据类型 * 变量名）到操作（取地址&、解引用*），再到实际应用（函数传址、动态内存、数据结构），指针贯穿了 C++ 编程的核心场景。