经典递归问题
阶乘和斐波那契数列。
经典递归问题 是 CoddyKit 上的免费 C Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。
经典问题
有些问题天然适合使用递归。学习这些经典问题，可以掌握能够重复使用的模式。
本课将介绍阶乘、斐波那契数、各位数字之和、最大公约数和反向输出。
阶乘
n 的阶乘等于 n 乘以 n 减 1 的阶乘，其中 1! 等于 1。
这是教科书式的递归：基本情况清晰，并且每一步只有一次递归调用。
#include <stdio.h>
long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main(void) {
printf("%ld\n", factorial(6));
return 0;
}斐波那契数
每个斐波那契数都等于它前面两个数之和。递归定义需要两个基本情况：fib(0)=0 和 fib(1)=1。
这个版本每一步都会进行两次调用。
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}运行斐波那契程序
下面是完整程序。fib(10) 应输出 55。
请注意，这个朴素版本会重复计算，因此 n 较大时运行速度很慢。
#include <stdio.h>
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
int main(void) {
printf("%d\n", fib(10));
return 0;
}各位数字之和
要计算一个数的各位数字之和，请使用 n % 10 取出最后一位数字，再对 n / 10 得到的其余部分进行递归。
基本情况是 n 达到 0。
int digit_sum(int n) {
if (n == 0) return 0;
return (n % 10) + digit_sum(n / 10);
}实际计算各位数字之和
对于 1234，总和是 1+2+3+4 = 10。让我们用一个完整程序进行确认。
#include <stdio.h>
int digit_sum(int n) {
if (n == 0) return 0;
return (n % 10) + digit_sum(n / 10);
}
int main(void) {
printf("%d\n", digit_sum(1234));
return 0;
}最大公约数
欧几里得算法天然适合使用递归。a 和 b 的 GCD 等于 b 和 a % b 的 GCD。
当 b 变为 0 时，a 就是答案。
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}GCD 完整程序
48 和 18 的 GCD 是 6。这个程序会将它输出。
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main(void) {
printf("%d\n", gcd(48, 18));
return 0;
}反转一个数
递归也可以驱动输出。通过在递归调用之后输出最后一位数字，就能自然地反转处理顺序。
这个辅助函数使用递归，将一个数的每一位数字分别输出。
#include <stdio.h>
void print_digits(int n) {
if (n == 0) return;
print_digits(n / 10);
printf("%d ", n % 10);
}
int main(void) {
print_digits(729);
printf("\n");
return 0;
}幂函数
将底数提升到指数次方同样可以用递归实现：base^exp 等于 base 乘以 base^(exp-1)。
基本情况是指数为 0，此时返回 1。
long power(int base, int exp) {
if (exp == 0) return 1;
return base * power(base, exp - 1);
}可复用的模式
请注意它们的共同结构：检查基本情况，然后将当前步骤与较小调用的结果组合起来。
一旦发现这个模式，许多问题都可以写成简短的递归函数。
快速检查
请选择正确的基本情况。
回顾
阶乘、斐波那契、数字和、GCD 和幂函数都遵循同一种递归模式：处理基本情况，然后将当前值与规模更小的子问题组合起来。
这些模板还可以应用于许多其他任务。
常见问题解答
「经典递归问题」课时是免费的吗？
是的 — 「经典递归问题」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。
「经典递归问题」这节课中我会学到什么？
阶乘和斐波那契数列。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 C Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「经典递归问题」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 C Academy 课中编写并运行代码吗？
能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。