本文用最通俗的语言讲解两个经典的递归问题，所有代码均为 C 语言实现，不涉及指针，适合正在学习函数与递归的读者。
一、青蛙跳台阶
1.1 这个问题从哪来？
小时候上楼梯，你有没有想过：如果每次可以跨 1 级或 2 级，那么上第 5 级楼梯有多少种走法？
这个问题和“青蛙跳台阶”一模一样。它其实是著名的斐波那契数列的一个实际应用场景——每一项都等于前两项之和。
1.2 问题描述
一只青蛙每次可以跳1 级或2 级台阶。问：跳上第n级台阶，总共有多少种不同的跳法？
我们先看几个小例子找找感觉：
| 台阶数 | 所有跳法 | 种数 |
|---|---|---|
| 1 | (1) | 1 |
| 2 | (1,1)、(2) | 2 |
| 3 | (1,1,1)、(1,2)、(2,1) | 3 |
| 4 | (1,1,1,1)、(1,1,2)、(1,2,1)、(2,1,1)、(2,2) | 5 |
规律出来了：从第 3 项开始，f(n) = f(n-1) + f(n-2)。
为什么？因为青蛙最后一步只有两种可能：
- 从n-1级跳 1 级上来 → 前面有f(n-1)种走法
- 从n-2级跳 2 级上来 → 前面有f(n-2)种走法
把这两种情况加起来，就是总数。
1.3 非递归解法（循环版）
不用递归，我们也能做。就像你爬楼梯时一步一步数上去，循环从 1 算到 n 就行。
为了代码简单，我们只保留最近的两项，用三个变量“接力”前进：
#include <stdio.h> /* 青蛙跳台阶 - 非递归（循环版） 思路：从第 1 级、第 2 级开始，一步步算到第 n 级 只用三个变量，像接力赛跑一样往前传递 / int frog_jump(int n) { / 处理特殊情况 */ if (n <= 0) return 0; if (n == 1) return 1; if (n == 2) return 2; int prev2 = 1; /* 代表 f(n-2)，即前两项中的前一项 / int prev1 = 2; / 代表 f(n-1)，即前两项中的后一项 / int current = 0; / 当前正在计算的这一级 */ int i; /* 从第 3 级开始，一直算到第 n 级 / for (i = 3; i <= n; i++) { current = prev1 + prev2; / 当前级 = 前两级之和 / prev2 = prev1; / 大家往前挪一步 */ prev1 = current; } return current; } int main() { int n; printf("请输入台阶数："); scanf("%d", &n); printf("跳上 %d 级台阶共有 %d 种跳法\n", n, frog_jump(n)); return 0; }核心思想：就像你爬楼梯时只记得“上两级有多少种走法”和“上一级有多少种走法”，就能算出这一级有多少种走法，更早的数据不需要记了。
1.4 递归解法
递归的写法非常自然，几乎就是把我们刚才的分析翻译成代码：
#include <stdio.h> /* 青蛙跳台阶 - 递归版 思路：f(n) = f(n-1) + f(n-2) 边界条件：1 级台阶有 1 种，2 级台阶有 2 种 / int frog_jump_recur(int n) { / 边界条件：递归到这里就不再往下拆了 */ if (n == 1) return 1; if (n == 2) return 2; /* 把大问题拆成两个子问题，结果相加 */ return frog_jump_recur(n - 1) + frog_jump_recur(n - 2); } int main() { int n; printf("请输入台阶数："); scanf("%d", &n); printf("跳上 %d 级台阶共有 %d 种跳法\n", n, frog_jump_recur(n)); return 0; }为什么能这样写？
想象青蛙站在第n级台阶上回头看，它最后一步只有两种来路：
- 从n-1级跳上来的 → 有多少种来路？问f(n-1)
- 从n-2级跳上来的 → 有多少种来路？问f(n-2)
一直问到n=1或n=2，这就是“边界”，边界知道了，一层层返回来就能算出答案。
小提示：递归代码虽然好看，但当
n比较大时（比如超过 40），会因为重复计算太多而变得很慢。平时写代码推荐用上面的循环版。
二、汉诺塔
2.1 这个问题从哪来？
汉诺塔（Hanoi）是一个古老的印度传说：
神庙里有三根金刚石柱子，第一根上套着 64 个大小不等的金盘，大的在下，小的在上。僧侣们要把这 64 个金盘从第一根柱子移到第三根柱子，规则是每次只能移动一个盘，且大盘不能压在小盘上。据说当所有盘子都移完时，世界就会毁灭。
当然，这只是个传说。但这个游戏确实是一个非常经典的递归思维训练题。
2.2 问题描述
有三根柱子：A（起始）、B（辅助）、C（目标）。A柱上有n个盘子，从上到下从小到大排列。要求把所有盘子从A移到C，每次只能移一个，大盘不能压小盘。
2.3 递归解法
这是汉诺塔最经典、最优雅的解法。核心思路就一句话：
把上面的
n-1个盘子先挪走，把最底下那个大盘子直接移到目标柱，再把那n-1个盘子移过来。
就像搬家：先把家具都搬到临时房间，把大床搬进主卧，再把家具从临时房间搬进来。
#include <stdio.h> /* 汉诺塔 - 递归版 参数说明： n ：要移动的盘子数量 from ：从哪根柱子移出 to ：移到哪根柱子 via ：借助哪根柱子（中转站） 思路： 把上面 n-1 个盘子从 from 移到 via（借助 to） 把第 n 个盘子从 from 直接移到 to 把 via 上的 n-1 个盘子移到 to（借助 from） / void hanoi(int n, char from, char to, char via) { / 边界条件：只有一个盘子，直接搬 */ if (n == 1) { printf("将盘子 1 从 %c 移动到 %c\n", from, to); return; } /* 第 1 步：把上面 n-1 个盘子搬到中转柱 */ hanoi(n - 1, from, via, to); /* 第 2 步：把最底下的大盘子搬到目标柱 */ printf("将盘子 %d 从 %c 移动到 %c\n", n, from, to); /* 第 3 步：把中转柱上的 n-1 个盘子搬到目标柱 / hanoi(n - 1, via, to, from); } int main() { int n; printf("请输入盘子个数："); scanf("%d", &n); / 从 A 柱移到 C 柱，B 柱作为中转 */ hanoi(n, 'A', 'C', 'B'); return 0; }运行结果（3 个盘子时）：
将盘子 1 从 A 移动到 C 将盘子 2 从 A 移动到 B 将盘子 1 从 C 移动到 B 将盘子 3 从 A 移动到 C 将盘子 1 从 B 移动到 A 将盘子 2 从 B 移动到 C 将盘子 1 从 A 移动到 C你可以拿三个大小不一的硬币在桌上摆一摆，完全吻合！
2.4 非递归解法（思路简述）
汉诺塔的非递归写法需要自己用数组模拟系统栈，手动记录每一步该做什么、做到哪了。代码量很大，逻辑也比较绕，对初学者不太友好。
其核心思想是：递归其实是系统在帮我们管理一个“任务清单”。非递归版本就是自己写代码维护这个清单——每遇到一个子问题就记下来，做完一个划掉一个。
如果你感兴趣，可以记住这个结论：汉诺塔的非递归 = 用循环 + 数组栈 手动模拟递归的过程。理解了递归的本质后，再回头挑战非递归会轻松很多。
对于汉诺塔问题，递归解法不仅代码最简洁，而且本身就是最优的（数学上已证明最少需要移动 2ⁿ-1 次），所以实际学习和面试中，掌握递归版本就足够了。
三、一句话总结
| 问题 | 非递归核心 | 递归核心 |
|---|---|---|
| 青蛙跳台阶 | 从第 1 级开始，一步步“接力”算到第 n 级 | f(n) = f(n-1) + f(n-2)，问到边界就回头 |
| 汉诺塔 | 自己用数组模拟栈，手动管理任务（较复杂） | 先把上面的盘子挪走，移最底下的，再把上面的挪回来 |
递归的精髓就三步：
1.找规律—— 大问题怎么拆成小问题？
2.写边界—— 小到什么程度可以直接给出答案？
3.相信递归—— 假设子问题已经解决，只管把它们拼起来。
希望这篇文章能帮你跨过递归这道坎！如果有疑问，欢迎在评论区交流。
