14、函数与递归 - 孙计奥 Notes

1、课程目标

掌握函数的定义、声明和调用
理解参数传递方式(值传递、指针传递)
掌握递归函数的实现
了解函数指针的使用

2、名词解释

术语	说明
函数声明	告诉编译器函数的存在（原型）
函数定义	函数的实际实现
形参	函数定义中的参数
实参	调用时传入的实际值
值传递	拷贝参数值，不影响原变量
指针传递	传递地址，可修改原变量
递归	函数调用自身
回调函数	通过函数指针调用的函数

3、代码实现

1. 函数基础

#include <stdio.h>

// 函数声明(原型)
int Add(int a, int b);
void PrintMessage(const char* msg);
int Factorial(int n);

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

void PrintMessage(const char* msg) {
    printf("[MSG] %s\n", msg);
}

int main() {
    printf("=== 函数基础 ===\n\n");
    
    // 函数调用
    int sum = Add(10, 20);
    printf("10 + 20 = %d\n", sum);
    
    PrintMessage("Hello Function!");
    
    return 0;
}

2. 参数传递方式

#include <stdio.h>

// 值传递: 不能修改原变量
void SwapByValue(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
    printf("  函数内: a=%d, b=%d\n", a, b);
}

// 指针传递: 可以修改原变量
void SwapByPointer(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 数组参数
void PrintArray(int arr[], int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("]\n");
}

// 修改数组
void FillArray(int* arr, int size, int value) {
    for (int i = 0; i < size; i++) {
        arr[i] = value;
    }
}

int main() {
    printf("=== 参数传递 ===\n\n");
    
    // 值传递
    printf("【值传递】\n");
    int x = 10, y = 20;
    printf("交换前: x=%d, y=%d\n", x, y);
    SwapByValue(x, y);
    printf("交换后: x=%d, y=%d (未改变)\n", x, y);
    
    // 指针传递
    printf("\n【指针传递】\n");
    printf("交换前: x=%d, y=%d\n", x, y);
    SwapByPointer(&x, &y);
    printf("交换后: x=%d, y=%d (已改变)\n", x, y);
    
    // 数组参数
    printf("\n【数组参数】\n");
    int arr[5] = {1, 2, 3, 4, 5};
    PrintArray(arr, 5);
    FillArray(arr, 5, 0);
    PrintArray(arr, 5);
    
    return 0;
}

3. 递归函数

#include <stdio.h>

// 阶乘
int Factorial(int n) {
    if (n <= 1) return 1;
    return n * Factorial(n - 1);
}

// 斐波那契
int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

// 二分查找(递归版)
int BinarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;
    if (arr[mid] > target)
        return BinarySearch(arr, left, mid - 1, target);
    return BinarySearch(arr, mid + 1, right, target);
}

int main() {
    printf("=== 递归函数 ===\n\n");
    
    // 阶乘
    printf("【阶乘】\n");
    for (int i = 0; i <= 10; i++) {
        printf("%d! = %d\n", i, Factorial(i));
    }
    
    // 斐波那契
    printf("\n【斐波那契】\n");
    printf("F(10) = %d\n", Fibonacci(10));
    
    // 二分查找
    printf("\n【二分查找】\n");
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int idx = BinarySearch(arr, 0, 6, 7);
    printf("查找7: 索引=%d\n", idx);
    
    return 0;
}

4. 函数指针

#include <stdio.h>

// 函数原型
int Add(int a, int b) { return a + b; }
int Sub(int a, int b) { return a - b; }
int Mul(int a, int b) { return a * b; }
int Div(int a, int b) { return b ? a / b : 0; }

// 函数指针类型
typedef int (*MathFunc)(int, int);

// 回调函数示例
void ProcessArray(int* arr, int size, int (*callback)(int)) {
    for (int i = 0; i < size; i++) {
        arr[i] = callback(arr[i]);
    }
}

int Double(int x) { return x * 2; }
int Square(int x) { return x * x; }

int main() {
    printf("=== 函数指针 ===\n\n");
    
    // 函数指针数组
    printf("【函数指针数组】\n");
    MathFunc funcs[] = {Add, Sub, Mul, Div};
    const char* names[] = {"+", "-", "*", "/"};
    
    int a = 10, b = 3;
    for (int i = 0; i < 4; i++) {
        printf("%d %s %d = %d\n", a, names[i], b, funcs[i](a, b));
    }
    
    // 回调函数
    printf("\n【回调函数】\n");
    int arr[] = {1, 2, 3, 4, 5};
    ProcessArray(arr, 5, Double);
    printf("翻倍后: ");
    for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
    printf("\n");
    
    return 0;
}

5、课后作业

5.1、作业1：实现排序函数

实现冒泡排序，接受函数指针作为比较函数。

5.2、作业2：汉诺塔

用递归实现汉诺塔问题。

5.3、作业3：计算器程序

使用函数指针数组实现简单计算器。