C语言递归函数完全指南

分类：算法 · 2026-05-23 更新

1. 什么是递归

递归是指函数直接或间接调用自身的行为。递归的核心思想是将大问题分解为与原问题相似的子问题，直到子问题足够简单可以直接求解。

一个完整的递归函数必须包含两个部分：

递归终止条件（基例）：当满足某条件时不再递归，直接返回结果
递归调用：将问题规模缩小，调用自身继续求解

2. 递归调用栈

每次函数调用都会在调用栈上创建一个新的栈帧（stack frame），保存函数参数、局部变量和返回地址。递归调用的层级过深会导致栈溢出。

/* 递归调用过程示例：计算阶乘 */ #include int factorial(int n) { if (n <= 1) /* 递归终止条件 */ return 1; return n * factorial(n - 1); /* 递归调用 */ } int main(void) { printf("5! = %d\n", factorial(5)); /* 输出: 120 */ return 0; }

3. 典型递归应用

3.1 斐波那契数列

/* 斐波那契数列：1, 1, 2, 3, 5, 8, 13, ... */ int fib(int n) { if (n <= 2) return 1; return fib(n - 1) + fib(n - 2); }

注意：朴素递归实现 fib() 存在大量重复计算，时间复杂度是指数级 O(2^n)。实际使用建议用动态规划优化。

3.2 汉诺塔

/* 汉诺塔：将 n 个盘子从 A 柱移动到 C 柱 */ void hanoi(int n, char from, char to, char aux) { if (n == 0) return; hanoi(n - 1, from, aux, to); printf("Move disk %d from %c to %c\n", n, from, to); hanoi(n - 1, aux, to, from); } /* 调用：hanoi(3, 'A', 'C', 'B'); */

汉诺塔的移动次数为 2^n - 1，时间复杂度 O(2^n)。

3.3 目录遍历

/* 递归遍历目录（Linux 示例） */ #include void traverse(const char *path) { DIR *dir = opendir(path); struct dirent *entry; char filepath[512]; while ((entry = readdir(dir)) != NULL) { if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0) continue; snprintf(filepath, sizeof(filepath), "%s/%s", path, entry->d_name); printf("%s\n", filepath); if (entry->d_type == DT_DIR) /* 递归进入子目录 */ traverse(filepath); } closedir(dir); }

4. 尾递归优化

尾递归是指递归调用是函数的最后一个操作（return 语句中只有递归调用，没有其他计算）。编译器可以对尾递归进行优化，避免创建新的栈帧。

/* 普通递归：需要保存之前的调用栈 */ int factorial_naive(int n, int acc) { if (n <= 1) return acc; return factorial_naive(n - 1, n * acc); /* 尾递归 */ }

在支持尾递归优化的编译器（如 GCC 带 -O2）中，上述代码会被优化为循环执行，不会造成栈溢出。

5. 递归转迭代

当递归深度无法确定或编译器不支持尾递归优化时，可以将递归改写为显式栈模拟递归过程。

/* 用显式栈模拟前序遍历二叉树 */ #include typedef struct TreeNode { int val; struct TreeNode *left, *right; } TreeNode; typedef struct Stack { TreeNode **data; int top, capacity; } Stack; void push(Stack *s, TreeNode *node) { if (s->top >= s->capacity) return; s->data[s->top++] = node; } TreeNode *pop(Stack *s) { return s->top > 0 ? s->data[--s->top] : NULL; } void preorder_iterative(TreeNode *root) { if (!root) return; Stack s = {malloc(sizeof(TreeNode*) * 100), 0, 100}; push(&s, root); while (s.top > 0) { TreeNode *node = pop(&s); printf("%d ", node->val); if (node->right) push(&s, node->right); if (node->left) push(&s, node->left); } free(s.data); }

6. 性能与注意事项

栈溢出风险：递归深度通常受限于栈大小（Linux 默认约 8MB），过深会崩溃
重复计算：如 fib() 的朴素实现，可用记忆化（memoization）优化
函数调用开销：每次调用有栈帧创建、参数传递、返回值处理等开销
可读性优先：对于简单问题（如遍历链表），递归写法更优雅

实战建议：在生产代码中，优先考虑使用迭代。如果必须用递归，评估最大递归深度（通常 < 10000 是安全的），并尽量使用尾递归形式。