四、递归函数
4.1 递归基础
#include <stdio.h>
// 递归要素：
// 1. 基线条件：停止递归的条件
// 2. 递归条件：调用自身的条件
// 阶乘：n! = n * (n-1)!
unsigned long long factorial(int n) {
// 基线条件
if (n <= 1) {
return 1;
}
// 递归条件
return n * factorial(n - 1);
}
// 斐波那契数列：F(n) = F(n-1) + F(n-2)
unsigned long long fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 最大公约数（欧几里得算法）
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
printf("5! = %llu\n", factorial(5));
printf("10! = %llu\n", factorial(10));
printf("fib(10) = %llu\n", fibonacci(10));
printf("fib(20) = %llu\n", fibonacci(20));
printf("gcd(48, 18) = %d\n", gcd(48, 18));
return 0;
}
4.2 经典递归示例
#include <stdio.h>
// 汉诺塔
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("移动盘子 1 从 %c 到 %c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to);
printf("移动盘子 %d 从 %c 到 %c\n", n, from, to);
hanoi(n - 1, aux, to, from);
}
// 二分查找（递归实现）
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;
} else if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
// 计算x的n次幂（快速幂）
double power(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n < 0) return 1 / power(x, -n);
double half = power(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
// 字符串反转（递归）
void reverseString(char* str, int left, int right) {
if (left >= right) return;
char temp = str[left];
str[left] = str[right];
str[right] = temp;
reverseString(str, left + 1, right - 1);
}
int main() {
printf("汉诺塔(3个盘子):\n");
hanoi(3, 'A', 'C', 'B');
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int index = binarySearch(arr, 0, 7, 7);
printf("查找7的位置: %d\n", index);
printf("2^10 = %.0f\n", power(2, 10));
printf("5^-2 = %f\n", power(5, -2));
char str[] = "Hello, World!";
printf("原字符串: %s\n", str);
reverseString(str, 0, strlen(str) - 1);
printf("反转后: %s\n", str);
return 0;
}
4.3 递归与迭代对比
#include <stdio.h>
#include <time.h>
// 递归实现斐波那契（效率低）
unsigned long long fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 迭代实现斐波那契（效率高）
unsigned long long fibIterative(int n) {
if (n <= 1) return n;
unsigned long long prev2 = 0, prev1 = 1, current;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// 尾递归优化（编译器可能优化）
unsigned long long fibTailRec(int n, unsigned long long a, unsigned long long b) {
if (n == 0) return a;
if (n == 1) return b;
return fibTailRec(n - 1, b, a + b);
}
int main() {
int n = 40;
// 尾递归版本
printf("fib(%d) = %llu (尾递归)\n", n, fibTailRec(n, 0, 1));
// 迭代版本
printf("fib(%d) = %llu (迭代)\n", n, fibIterative(n));
return 0;
}
五、函数指针
5.1 函数指针基础
#include <stdio.h>
// 函数指针：指向函数的指针变量
// 普通函数
int add(int a, int b) {
return a + b;
}
int subtract(int a, int b) {
return a - b;
}
int multiply(int a, int b) {
return a * b;
}
int divide(int a, int b) {
return b != 0 ? a / b : 0;
}
int main() {
// 声明函数指针：返回值类型 (*指针名)(参数类型列表)
int (*pFunc)(int, int);
// 指向add函数
pFunc = add;
printf("add: %d\n", pFunc(10, 5));
// 指向subtract函数
pFunc = subtract;
printf("subtract: %d\n", pFunc(10, 5));
// 指向multiply函数
pFunc = multiply;
printf("multiply: %d\n", pFunc(10, 5));
// 指向divide函数
pFunc = divide;
printf("divide: %d\n", pFunc(10, 5));
return 0;
}
5.2 函数指针作为参数
#include <stdio.h>
// 计算函数类型
typedef int (*Operation)(int, int);
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
int multiply(int a, int b) { return a * b; }
int divide(int a, int b) { return b != 0 ? a / b : 0; }
// 函数指针作为参数（回调函数）
int calculate(int a, int b, Operation op) {
return op(a, b);
}
// 遍历数组并应用函数
void map(int arr[], int size, int (*func)(int)) {
for (int i = 0; i < size; i++) {
arr[i] = func(arr[i]);
}
}
int square(int x) {
return x * x;
}
int doubleValue(int x) {
return x * 2;
}
// 函数指针数组
void printMenu() {
printf("1. 加法\n");
printf("2. 减法\n");
printf("3. 乘法\n");
printf("4. 除法\n");
}
int main() {
// 使用函数指针作为参数
printf("10 + 5 = %d\n", calculate(10, 5, add));
printf("10 - 5 = %d\n", calculate(10, 5, subtract));
printf("10 * 5 = %d\n", calculate(10, 5, multiply));
printf("10 / 5 = %d\n", calculate(10, 5, divide));
// 使用map函数
int numbers[] = {1, 2, 3, 4, 5};
int size = sizeof(numbers) / sizeof(numbers[0]);
map(numbers, size, square);
printf("平方后: ");
for (int i = 0; i < size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
// 函数指针数组
Operation ops[] = {add, subtract, multiply, divide};
printMenu();
int choice = 1;
printf("结果: %d\n", ops[choice - 1](10, 5));
return 0;
}
5.3 函数指针作为返回值
#include <stdio.h>
typedef int (*Operation)(int, int);
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
int multiply(int a, int b) { return a * b; }
int divide(int a, int b) { return b != 0 ? a / b : 0; }
// 返回函数指针
Operation getOperation(char op) {
switch(op) {
case '+': return add;
case '-': return subtract;
case '*': return multiply;
case '/': return divide;
default: return NULL;
}
}
int main() {
Operation op = getOperation('+');
if (op != NULL) {
printf("10 + 5 = %d\n", op(10, 5));
}
op = getOperation('*');
if (op != NULL) {
printf("10 * 5 = %d\n", op(10, 5));
}
return 0;
}
5.4 qsort中的函数指针
#include <stdio.h>
#include <stdlib.h>
// 比较函数（供qsort使用）
int compareInt(const void* a, const void* b) {
int ia = *(int*)a;
int ib = *(int*)b;
return ia - ib; // 升序
// return ib - ia; // 降序
}
// 比较字符串长度
int compareStringLength(const void* a, const void* b) {
const char* sa = *(const char**)a;
const char* sb = *(const char**)b;
return strlen(sa) - strlen(sb);
}
// 比较结构体
typedef struct {
char name[50];
int age;
} Person;
int comparePersonByAge(const void* a, const void* b) {
const Person* pa = (const Person*)a;
const Person* pb = (const Person*)b;
return pa->age - pb->age;
}
int comparePersonByName(const void* a, const void* b) {
const Person* pa = (const Person*)a;
const Person* pb = (const Person*)b;
return strcmp(pa->name, pb->name);
}
int main() {
// 整数数组排序
int numbers[] = {5, 2, 8, 1, 9, 3, 7, 4, 6};
int size = sizeof(numbers) / sizeof(numbers[0]);
qsort(numbers, size, sizeof(int), compareInt);
printf("排序后的整数: ");
for (int i = 0; i < size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
// 字符串数组排序
const char* words[] = {"apple", "banana", "pear", "grape", "kiwi"};
int wsize = sizeof(words) / sizeof(words[0]);
qsort(words, wsize, sizeof(const char*), compareStringLength);
printf("按长度排序: ");
for (int i = 0; i < wsize; i++) {
printf("%s ", words[i]);
}
printf("\n");
// 结构体数组排序
Person persons[] = {
{"张三", 25},
{"李四", 30},
{"王五", 22},
{"赵六", 28}
};
int psize = sizeof(persons) / sizeof(persons[0]);
qsort(persons, psize, sizeof(Person), comparePersonByAge);
printf("按年龄排序:\n");
for (int i = 0; i < psize; i++) {
printf(" %s: %d岁\n", persons[i].name, persons[i].age);
}
return 0;
}
六、内联函数
#include <stdio.h>
// 内联函数：建议编译器将函数代码直接插入调用处
// 适用于短小、频繁调用的函数
static inline int max(int a, int b) {
return a > b ? a : b;
}
static inline int min(int a, int b) {
return a < b ? a : b;
}
static inline int square(int x) {
return x * x;
}
// 宏定义 vs 内联函数
#define MAX_MACRO(a, b) ((a) > (b) ? (a) : (b))
#define SQUARE_MACRO(x) ((x) * (x))
int main() {
int a = 10, b = 20;
// 内联函数调用（可能被内联展开）
printf("最大值: %d\n", max(a, b));
printf("最小值: %d\n", min(a, b));
printf("平方: %d\n", square(5));
// 宏展开（预处理阶段）
printf("MAX宏: %d\n", MAX_MACRO(a, b));
printf("SQUARE宏: %d\n", SQUARE_MACRO(5));
// 内联函数的优势：类型安全、参数只计算一次
int x = 5;
printf("square(x++): %d, x=%d\n", square(x++), x); // x++执行一次
x = 5;
printf("SQUARE_MACRO(x++): %d, x=%d\n", SQUARE_MACRO(x++), x); // x++执行两次
return 0;
}
