函数进阶 - 递归与数组参数

📋 今日学习内容总览

1. 函数定义与调用复习
2. 函数递归详解
3. 数组作为函数参数
4. 标识符的作用域与可见性
5. 变量的生命周期
6. 存储类别关键字

---

一、函数基础回顾

1. 函数定义的位置

方式1: main函数之前

int add(int a, int b)  // 定义在main前
{
    return a + b;
}

int main(void)
{
    int result = add(3, 5);  // 直接使用
    return 0;
}

方式2: main函数之后(需要声明)

// 函数声明(函数头 + 分号)
int add(int a, int b);

int main(void)
{
    int result = add(3, 5);  // 使用前已声明
    return 0;
}

// 函数定义
int add(int a, int b)
{
    return a + b;
}

2. 函数设计原则

1. 功能单一原则 - 一个函数只做一件事
2. 复用性 - 考虑函数是否会被反复使用
3. 数据流清晰 - 明确输入输出

3. 数据传递方式

值传递:

void swap(int a, int b)  // 形参只是实参的副本
{
    int t = a;
    a = b;
    b = t;
    // main中的a, b不会改变!
}

int main(void)
{
    int a = 10, b = 20;
    swap(a, b);  // 实参值传给形参
    printf("%d %d\n", a, b);  // 输出: 10 20
}

全局变量(函数间共享数据):

int count = 0;  // 全局变量

void increment()
{
    count++;  // 直接修改全局变量
}

---

二、函数递归 ⭐

1. 什么是递归?

定义: 函数自己调用自己

特点:

• 是一种特殊的循环
• 必须有结束条件,否则栈溢出
• 可以替代循环,但效率可能较低

2. 递归解题思路

两大要素:

1. 递推关系 - 问题n与问题n-1的关系
2. 递归结束条件 - 最简单情况的解

3. 递归实现1+2+3+...+100

分析过程:

sum(100) = sum(99) + 100
           ↓
sum(99) = sum(98) + 99
          ↓
sum(98) = sum(97) + 98
          ...
sum(2) = sum(1) + 2
         ↓
sum(1) = 1  (递归结束)

递推关系: sum(n) = sum(n-1) + n
结束条件: n == 1

代码实现:

int sum(int n)
{
    // 递归结束条件
    if (n == 1)
    {
        return 1;
    }
    else  // 继续递归
    {
        return sum(n-1) + n;
    }
}

// 调用
int main(void)
{
    int result = sum(100);
    printf("1+2+...+100 = %d\n", result);
    return 0;
}

4. 递归实现阶乘

需求: 计算 n! = 1×2×3×...×n

分析:

fact(5) = 5 × fact(4)
          ↓
fact(4) = 4 × fact(3)
          ↓
fact(3) = 3 × fact(2)
          ↓
fact(2) = 2 × fact(1)
          ↓
fact(1) = 1  (递归结束)

递推关系: fact(n) = n × fact(n-1)
结束条件: n == 1

代码实现:

int factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    else
    {
        return n * factorial(n-1);
    }
}

// 使用
int main(void)
{
    printf("5! = %d\n", factorial(5));  // 输出: 120
    return 0;
}

5. 经典递归问题:汉诺塔

问题: 将n个盘子从A柱移到C柱(借助B柱)

递归思路:

1. 将n-1个盘子从A移到B(借助C)
2. 将第n个盘子从A移到C
3. 将n-1个盘子从B移到C(借助A)

void hanoi(int n, char A, char B, char C)
{
    if (n == 1)
    {
        printf("移动盘子1: %c -> %c\n", A, C);
    }
    else
    {
        hanoi(n-1, A, C, B);  // 1. n-1个A->B
        printf("移动盘子%d: %c -> %c\n", n, A, C);  // 2. 第n个A->C
        hanoi(n-1, B, A, C);  // 3. n-1个B->C
    }
}

6. 递归的限制

⚠️ 注意事项:

1. 层次不能太深(栈空间有限,默认8M)
2. 效率通常比循环低
3. 某些问题用递归更自然(如树、图遍历)

---

三、数组作为函数参数 ⭐⭐⭐

1. 数组元素作为参数(普通变量)

void printElement(int ele)
{
    printf("%d\n", ele);
}

int main(void)
{
    int a[5] = {1, 2, 3, 4, 5};
    printElement(a[0]);  // 传递单个元素,值传递
    return 0;
}

2. 整个数组作为参数

重要概念:

• 传递的不是整个数组
• 传递的是首元素地址(指针)
• 函数可以通过地址访问整个数组

原因: 数组的三大特点

• 连续性 - 内存连续
• 单一性 - 类型相同
• 有序性 - 按序存放

3. 一维整型数组作为参数

形式1: 数组形式(推荐)

void printArray(int a[], int n)  // a[]只是形式,本质是指针
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

形式2: 指针形式(本质)

void printArray(int *a, int n)  // 本质:a是指针变量
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

调用方式:

int main(void)
{
    int a[10] = {1, 2, 3, 4, 5};
    printArray(a, 5);  // 传数组名(首元素地址)和长度
    return 0;
}

关键点:

• 形参: 数组形式 + 数组长度
• 实参: 数组名 + 实际长度
• ⚠️ sizeof(a) 在函数内是指针大小,不是数组大小!

4. 数组参数实战练习

练习1: 找最大值

int findMax(int a[], int n)
{
    int max = a[0];
    int i;
    
    for (i = 1; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
    }
    
    return max;
}

练习2: 数组逆序

void reverseArray(int a[], int n)
{
    int i, temp;
    
    for (i = 0; i < n/2; i++)
    {
        temp = a[i];
        a[i] = a[n-1-i];
        a[n-1-i] = temp;
    }
}

练习3: 数组排序

// 冒泡排序
void bubbleSort(int a[], int n)
{
    int i, j, temp;
    
    for (i = 1; i < n; i++)
    {
        for (j = 0; j < n-i; j++)
        {
            if (a[j] > a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

练习4: 数组查找

// 返回下标,未找到返回-1
int search(int a[], int n, int key)
{
    int i;
    
    for (i = 0; i < n; i++)
    {
        if (a[i] == key)
        {
            return i;  // 找到,返回下标
        }
    }
    
    return -1;  // 未找到
}

5. 一维字符数组作为参数

特点: 字符串有'\0'结束标志,不需要传长度!

实现strlen

int Strlen(char s[])  // 或 char *s
{
    int count = 0;
    
    while (s[count] != '\0')
    {
        count++;
    }
    
    return count;
}

实现strcpy

void Strcpy(char dest[], char src[])
{
    int i = 0;
    
    // 逐个复制字符
    while (src[i] != '\0')
    {
        dest[i] = src[i];
        i++;
    }
    
    dest[i] = '\0';  // 添加结束符
}

实现strcat

void Strcat(char dest[], char src[])
{
    int i = 0, j = 0;
    
    // 1. 找到dest的'\0'位置
    while (dest[i] != '\0')
    {
        i++;
    }
    
    // 2. 从'\0'位置开始复制src
    while (src[j] != '\0')
    {
        dest[i] = src[j];
        i++;
        j++;
    }
    
    // 3. 添加'\0'
    dest[i] = '\0';
}

实现strcmp

int Strcmp(char s1[], char s2[])
{
    int i = 0;
    
    // 逐个字符比较
    while (s1[i] != '\0' && s2[i] != '\0')
    {
        if (s1[i] != s2[i])
        {
            return s1[i] - s2[i];  // 返回差值
        }
        i++;
    }
    
    // 处理长度不同的情况
    return s1[i] - s2[i];
}

6. 二维数组作为参数

重要: 列数不能省略!

整型二维数组

// 形式1: 数组形式
void printArray(int a[3][4], int row)
{
    int i, j;
    
    for (i = 0; i < row; i++)
    {
        for (j = 0; j < 4; j++)
        {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

// 形式2: 指针形式(本质)
void printArray(int (*a)[4], int row)
{
    // a是指向包含4个int的数组的指针
}

// 调用
int main(void)
{
    int a[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
    printArray(a, 3);  // 传数组名和行数
    return 0;
}

字符型二维数组(多个字符串)

void printStrings(char s[][10], int row)
{
    int i;
    
    for (i = 0; i < row; i++)
    {
        printf("%s\n", s[i]);
    }
}

int main(void)
{
    char s[3][10] = {"hello", "world", "china"};
    printStrings(s, 3);
    return 0;
}

---

四、标识符的作用域与可见性

1. 作用域

局部作用域: {} 内部

int main(void)
{
    int a = 10;  // a的作用域: main函数内
    {
        int b = 20;  // b的作用域: 这个代码块内
    }
    // b在这里不可见
    return 0;
}

全局作用域: 不在任何 {} 内

int count = 0;  // 全局作用域

void func()
{
    count++;  // 可以访问全局变量
}

2. 可见性规则

规则1: 先定义,后使用

printf("%d", a);  // ❌ 错误
int a = 10;

规则2: 同一作用域不能有同名标识符

int a = 10;
int a = 20;  // ❌ 错误

规则3: 不同作用域同名标识符互不影响

int a = 10;  // 全局a

void func()
{
    int a = 20;  // 局部a,与全局a无关
}

规则4: 内层屏蔽外层(就近原则)

int a = 10;  // 全局a

int main(void)
{
    int a = 20;  // 局部a屏蔽全局a
    printf("%d\n", a);  // 输出: 20
    return 0;
}

---

五、变量的生命周期

1. 局部变量

定义: 在 {} 内定义的变量

生命周期:

• 创建: 程序执行到定义语句时
• 销毁: 程序执行到作用域结束时

void func()
{
    int a = 10;  // 进入函数时创建
    printf("%d", a);
}  // 退出函数时销毁

2. 全局变量

定义: 不在任何 {} 内的变量

生命周期:

• 创建: 程序开始运行时
• 销毁: 程序结束时

int count = 0;  // 程序开始时创建

int main(void)
{
    count++;
    return 0;
}  // 程序结束时销毁

---

六、存储类别关键字

1. auto(自动存储)

int main(void)
{
    auto int a = 10;  // 默认就是auto,一般省略
    // 存储在栈上,自动申请,自动释放
    return 0;
}

2. static(静态存储)

特点:

• 存储在静态区/全局区
• 只能用常量初始化,不能用变量
• 值具有继承性(保留上次的值)
• 只初始化一次

例子:

void func()
{
    static int count = 0;  // 只初始化一次
    count++;
    printf("%d ", count);
}

int main(void)
{
    func();  // 输出: 1
    func();  // 输出: 2
    func();  // 输出: 3
    return 0;
}

3. register(寄存器)

建议编译器将变量存储在寄存器中(已过时)

4. extern(外部声明)

声明变量在其他文件中定义

---

七、内存分区(五大区域)

---

🎯 重点总结

必须掌握

1. ✅ 递归的两大要素(递推关系+结束条件)
2. ✅ 数组作为参数的本质(传地址)
3. ✅ 一维数组参数需要传长度
4. ✅ 二维数组参数列数不能省略
5. ✅ 字符数组参数不需要传长度

重要概念

1. ✅ 作用域(局部/全局)
2. ✅ 可见性规则(就近原则)
3. ✅ 生命周期(创建/销毁时机)
4. ✅ static的特殊性(值继承)

调试技巧

// 加打印调试
printf("DEBUG: i = %d\n", i);
printf("DEBUG: 进入if分支\n");

继续加油!💪