递归函数就是在函数的定义中使用函数自身的方法。这种函数调用自身的方式可以将一个复杂的问题逐步简化为相同类型的较简单问题。
关键要素
1. 终止条件
这是递归函数中最重要的部分。如果没有终止条件，函数会一直调用自身，导致栈溢出（程序运行时栈空间耗尽）。终止条件用于确定何时停止递归调用，返回一个明确的值。
- 例如，在计算斐波那契数列的函数中：
c
int fibonacci(int n) {
if (n == 0 || n == 1) { // 终止条件，当n为0或1时，返回n
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
在这个函数里，当 n 等于0或者1时，函数就不再递归调用，而是直接返回 n 的值，这就是终止条件。
2. 递归调用
在满足非终止条件的情况下，函数会调用自身，并且每次调用时，问题的规模应该逐渐减小，使得最终能够达到终止条件。
- 还是以斐波那契数列为例， return fibonacci(n - 1) + fibonacci(n - 2); 这部分就是递归调用。它表示斐波那契数列的第 n 项等于第 n - 1 项和第 n - 2 项之和。每次递归调用都会使 n 的值减小，直到 n 等于0或者1，达到终止条件。
工作原理
递归函数的执行过程可以用栈来理解。每当一个函数被调用时，系统会为这个函数分配一块栈空间，用于存储函数的参数、局部变量和返回地址等信息。
- 当一个递归函数调用自身时，新的函数调用会在栈顶分配新的空间，保存新的参数和局部变量等。
- 以 fibonacci(4) 为例，计算过程如下：
- 首先调用 fibonacci(4) ，在栈中为这个函数调用分配空间。
- 由于 n 不等于0或1，所以执行 return fibonacci(3) + fibonacci(2); 。此时，先计算 fibonacci(3) ，系统会在栈顶为 fibonacci(3) 的调用分配新空间。
- 对于 fibonacci(3) ，又会执行 return fibonacci(2) + fibonacci(1); ，继续在栈顶为新的 fibonacci(2) 调用分配空间。
- 这个过程会一直持续，直到达到终止条件 n = 0 或 n = 1 。当达到终止条件后，函数开始返回，从栈顶的函数开始，依次计算并释放栈空间，最终得到 fibonacci(4) 的结果。
应用场景
1. 数学计算
- 阶乘计算：除了前面提到的阶乘函数 factorial ，还有一些其他的数学公式也可以用递归实现。例如组合数的计算，组合数 C(n, k) （表示从 n 个不同元素中取出 k 个元素的组合数）可以用以下递归公式表示： C(n, k) = C(n - 1, k - 1) + C(n - 1, k) ，同时 C(n, 0) = C(n, n) = 1 作为终止条件。
c
int combination(int n, int k) {
if (k == 0 || k == n) {
return 1;
} else {
return combination(n - 1, k - 1) + combination(n - 1, k);
}
}
- 幂运算：计算一个数 x 的 n 次幂。可以用递归方式实现，当 n 为偶数时， x^n = (x^(n/2))^2 ；当 n 为奇数时， x^n = x * (x^(n - 1)) ，终止条件是当 n = 0 时，返回1。
c
double power(double x, int n) {
if (n == 0) {
return 1;
} else if (n % 2 == 0) {
double temp = power(x, n / 2);
return temp * temp;
} else {
return x * power(x, n - 1);
}
}
2. 数据结构遍历
- 二叉树遍历：二叉树是一种常见的数据结构，它有根节点、左子树和右子树。
- 前序遍历：先访问根节点，然后递归地遍历左子树，再递归地遍历右子树。
c
// 二叉树节点结构体定义
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void preorderTraversal(TreeNode* root) {
if (root!= NULL) {
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
- 中序遍历：先递归地遍历左子树，然后访问根节点，再递归地遍历右子树。
c
void inorderTraversal(TreeNode* root) {
if (root!= NULL) {
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
}
- 后序遍历：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。
c
void postorderTraversal(TreeNode* root) {
if (root!= NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
3. 分治法问题
- 汉诺塔问题：有三根柱子A、B、C。开始时，在A柱子上有 n 个圆盘，这些圆盘大小不同，且按照从下到上圆盘大小递减的顺序排列。目标是将所有圆盘从A柱子移动到C柱子，在移动过程中可以借助B柱子，并且要求每次只能移动一个圆盘，且大盘不能放在小盘上面。
c
// 将n个圆盘从from柱，借助aux柱，移动到to柱
void hanoi(int n, char from, char aux, char to) {
if (n == 1) {
printf("将圆盘1从%c柱移动到%c柱\n", from, to);
} else {
hanoi(n - 1, from, to, aux);
printf("将圆盘%d从%c柱移动到%c柱\n", n, from, to);
hanoi(n - 1, aux, from, to);
}
}
在个函数中，通过不断地将问题分解为规模更小的子问题（每次减少一个圆盘的移动问题），并利用递归解决这些子问题，最终实现了整个汉诺塔问题的求解。