本文用最通俗的语言讲解两个经典的递归问题所有代码均为 C 语言实现不涉及指针适合正在学习函数与递归的读者。一、青蛙跳台阶1.1 这个问题从哪来小时候上楼梯你有没有想过如果每次可以跨 1 级或 2 级那么上第 5 级楼梯有多少种走法这个问题和“青蛙跳台阶”一模一样。它其实是著名的斐波那契数列的一个实际应用场景——每一项都等于前两项之和。1.2 问题描述一只青蛙每次可以跳1 级或2 级台阶。问跳上第n级台阶总共有多少种不同的跳法我们先看几个小例子找找感觉台阶数所有跳法种数1(1)12(1,1)、(2)23(1,1,1)、(1,2)、(2,1)34(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)一直问到n1或n2这就是“边界”边界知道了一层层返回来就能算出答案。小提示递归代码虽然好看但当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.相信递归—— 假设子问题已经解决只管把它们拼起来。希望这篇文章能帮你跨过递归这道坎如果有疑问欢迎在评论区交流。