C 递归
递归
递归是一种让函数自身被调用的技术。这种技术可以将复杂的问题分解成更容易解决的简单问题。
递归可能有点难理解。弄明白它工作原理的最佳方法是进行实验。
递归示例
两个数相加很容易，但计算一系列数字的和就比较复杂了。下面的示例使用递归将一系列数字相加，并将其分解为简单的两个数相加:
示例
使用递归计算 1 到 10 之间所有数字的和:
#include <stdio.h>
int sum(int k);
int main() {
int result = sum(10);
printf("%d", result);
return 0;
}
int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
示例详解
当调用 sum() 函数时，它会将参数 k 添加到小于 k 的所有数字之和中，并返回结果。当 k 等于 0 时，函数返回 0。程序运行时遵循以下步骤:
10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
由于当k为0时该函数不会调用自身，因此程序在此处停止并返回结果。
开发者在使用递归时应格外谨慎，因为很容易写出永不终止的函数，或者占用过多内存或处理器资源的函数。然而，如果编写得当，递归可以是一种非常高效且数学上优雅的编程方法。
示例
使用递归从 5 开始倒数:
#include <stdio.h>
void countdown(int n);
int main() {
countdown(5);
return 0;
}
void countdown(int n) {
if (n > 0) {
printf("%d ", n);
countdown(n - 1);
}
}
该函数会调用自身，每次调用时使用 n - 1，直到 n 变为 0。
使用递归计算阶乘
本示例使用递归函数计算 5 的阶乘:
示例
#include <stdio.h>
int factorial(int n);
int main() {
printf("Factorial of 5 is %d", factorial(5));
return 0;
}
int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}
阶乘是指将一个数依次乘以它前面的所有数，直到 1。
例如，5 的阶乘是:5 * 4 * 3 * 2 * 1 = 120。
根据定义，0! 也等于 1。
