🪜 递推算法

爬楼梯时，你总能站在上一级台阶上再迈一步。递推算法就是抓住这种「后一步靠前一步」的规律：从已知的第一级开始，一级一级把后面的答案推出来。

考纲知识点：递推算法基本思想、递推关系式推导

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 四级

📚

先学一学

花 5 分钟读完下面 4 课，再去闯关就不慌啦

🐰 递推：排队报数，一个接一个

全班排队报数：第 1 个人喊 1，第 2 个人听到「1」就喊 2，第 3 个人听到「2」就喊 3……每个后一个人只靠前一个人就能喊出自己。递推就是这个思路：先有开头几个已知数，再按规律一步步推出后面的数。最有名的例子是斐波那契（兔子）数列：

🐇 斐波那契数列的规律

第 1 项和第 2 项都是 1，从第 3 项开始，每一项 = 前两项相加：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
看看：2 = 1+1，3 = 1+2，5 = 2+3，8 = 3+5。第 10 项是 55。

💡 口诀：前两项打头，后面每一项都等于前两项之和。

📜 递推关系式：像数学公式一样写下来

用 F 表示第几项：F(1)=1、F(2)=1（这叫初始条件）；当 n ≥ 3 时 F(n)=F(n-1)+F(n-2)（这叫递推关系式）。

💡 口诀：递推 = 初始条件 + 递推关系式；有了这两样，就能一路推到天边。

🪜 推导递推式：爬楼梯想最后一步

问题：小明爬楼梯，一次可以上 1 级或 2 级。爬到第 10 级一共有多少种走法？

🤔 关键一问：最后一步从哪来？

要到第 10 级，最后一步只能从第 9 级迈 1 级，或从第 8 级迈 2 级。所以：到10级的方法 = 到9级的方法 + 到8级的方法。写成递推：f(n) = f(n-1) + f(n-2)，跟斐波那契一模一样！

💡 口诀：推递推式，就问「最后一步有哪几种来法」，把它们加起来。

🧮 从 1 级推到 10 级

初始：f(1)=1（只能迈1级）、f(2)=2（1+1 或 2）。然后：
f(3)=f(2)+f(1)=3，f(4)=f(3)+f(2)=5，f(5)=8，f(6)=13，f(7)=21，f(8)=34，f(9)=55，f(10)=89。

💡 口诀：一步一步从小往大推，答案藏在前面已经算好的数里。

💻 用数组实现递推：一格一格填答案

电脑最擅长「照规律重复算」，把每个算好的答案存进数组，后面的格子直接用前面的：

🧪 读代码：算斐波那契第 10 项

看得懂就好，不用背：

int f[20];
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= 10; i++)
f[i] = f[i - 1] + f[i - 2];
cout << f[10];

先填好前两格，循环从第 3 格一路算到第 10 格，每格都用「上一格 + 上上一格」。最后输出 55。

💡 口诀：数组一格一格存；f[i]=f[i-1]+f[i-2]，顺着小号填到大号。

🆚 递推 vs 递归：顺推和倒拆

📊 一张表看懂区别

· 递推：从第 1 项开始往大数方向一步步算，靠循环（for）实现。
· 递归：从第 n 项开始往回拆成小问题，靠「函数调用自己」实现，拆到头再一层层返回。
同一个斐波那契，递推是「从 1 往上加」，递归是「从 n 往下拆」。四级主要考递推，递归记个印象就好。

💡 口诀：递推从小往大「顺水推舟」，递归从大往小「刨根问底」。

🌟 行业实际：递推到处都有

游戏算「角色升到 10 级要多少经验」、银行算复利、铺地板算铺法、走路导航算最短路径……很多高级算法（比如动态规划）的第一步，都是先找出递推关系式。会推式子，是算法高手的看家本领。

💡 口诀：看到「后一步能由前一步推出」，就想到递推关系式。

🎯

闯关小锦囊 · 考点提醒

🎮

学完了？来闯关！

下面 15 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。