C Academy · 课时

递归的工作原理

Q: 「递归的工作原理」这节课中我会学到什么？

基本情况和调用栈。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

基本情况和调用栈。

递归的工作原理 是 CoddyKit 上的免费 C Academy 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

什么是递归

递归是指函数调用自身来解决问题。每次调用都会处理原问题中更小的一部分。

在 C 语言中，任何函数都可以调用自身，只要调用最终能够停止。

基本情况

每个递归函数都需要一个基本情况：在满足该条件时，函数停止调用自身并直接返回。

如果没有基本情况，函数就会不断调用自身，最终导致程序崩溃。

int countdown(int n) {
    if (n == 0) return 0; /* base case */
    return countdown(n - 1);
}

递归情况

递归情况是指函数使用发生变化的参数调用自身的部分。

该参数必须逐步接近基本情况，否则递归永远不会结束。

int sum_to(int n) {
    if (n == 0) return 0;       /* base case */
    return n + sum_to(n - 1);   /* recursive case */
}

第一个完整程序

让我们运行一个使用递归计算 1 到 5 之和的完整程序。

结果应为 15。

#include <stdio.h>

int sum_to(int n) {
    if (n == 0) return 0;
    return n + sum_to(n - 1);
}

int main(void) {
    printf("%d\n", sum_to(5));
    return 0;
}

跟踪调用过程

手动跟踪递归过程会很有帮助。对于 sum_to(3)：

sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0

接着，各次调用依次向上返回：先返回 1，再返回 3，最后返回 6。

调用栈

每次函数调用都会在调用栈中获得自己的空间，用来保存参数和局部变量。

递归深入时，栈帧会不断堆积。调用返回后，它的栈帧会被移除，控制权回到调用者。

展开与回溯

递归分为两个阶段。展开阶段会不断调用自身，逐步接近基本情况。

回溯阶段从基本情况返回，然后每次调用利用返回值完成自己的工作。

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main(void) {
    printf("%d\n", factorial(4));
    return 0;
}

返回值逐层传回

更深层调用返回的值，会被发起该调用的调用使用。

这就是顺序很重要的原因：最深层的调用先完成，然后结果在沿栈向上返回的过程中逐步组合。

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

递归过程中的输出

您可以在递归调用之前或之后输出。调用前输出会显示数字逐步向下，调用后输出会显示数字逐步向上返回。

#include <stdio.h>

void down(int n) {
    if (n == 0) return;
    printf("%d ", n);
    down(n - 1);
}

int main(void) {
    down(5);
    printf("\n");
    return 0;
}

在向上返回时输出

将 printf 放到递归调用之后，输出顺序就会反转。最深层的调用会先输出。

这样输出的是 1 2 3 4 5，而不是 5 4 3 2 1。

#include <stdio.h>

void up(int n) {
    if (n == 0) return;
    up(n - 1);
    printf("%d ", n);
}

int main(void) {
    up(5);
    printf("\n");
    return 0;
}

请记住两条规则

正确的递归函数遵循两条规则：

1. 至少有一个无需递归即可返回的基本情况。
2. 每次递归调用都会让参数更接近某个基本情况。

违反其中任何一条规则，程序都会无限循环。

快速检查

检验您对递归基础知识的理解。

回顾

递归通过对更小的输入调用自身来解决问题。您始终需要一个用于停止的基本情况，以及一个逐步接近它的递归情况。

每次调用都会使用一个栈帧；调用回溯时，结果会逐层传回。

常见问题解答

「递归的工作原理」课时是免费的吗？

是的 — 「递归的工作原理」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「递归的工作原理」这节课中我会学到什么？

基本情况和调用栈。你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「递归的工作原理」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy