定义 10.1.1 · 递推
递推就是先求出较小情况的值，再用它们去算出较大情况的值。
组合计数 · 第 10 章
递推
把一个大的计数问题从小问题一步步搭起来：每个答案都是前面几个答案的和。
10.10%
递推基础
在本节中，你将能够 从最下面一级开始填表，数出爬上楼梯的方法数。
Jeff 要爬 6 级台阶，每步跨 1 级或 2 级。把所有爬法一个个列出来，又慢又容易出错。能不能让小楼梯替你干活？
核心想法是这样的：想想 Jeff 的最后一步。他是从下面 1 级跨上顶层，或者从下面 2 级跨上顶层。
所以，到达顶层的方法数，就是到达那两级台阶的方法数之和。从最下面开始，一级一级地填一张表。
注意：表里的每个格子，只需要用到它前面紧挨着的几个格子。
动手探索先玩，再学公式
认识概念
注 10.1.2
看： 这些数正好是斐波那契数列。这是因为我们这个数列的递推式和斐波那契数列的递推式完全一样。不过，并不是所有递推问题都会这样。
看例题先预测，再揭晓
例 10.1
Jeff 要爬一段 6 级的楼梯。如果他每次可以爬 1 级或 2 级，他有多少种不同的方法爬到顶？
- 1
你可以分类讨论，但那样太费时间。先解决小的情况。Jeff 到达第 0 级（也就是地面）有多少种方法？
先预测一下：
自己做
习题 10.4.1
Jeff 要爬一段 7 级的楼梯。如果他每次可以爬 1 级或 2 级，他有多少种方法爬到顶？
竞赛角真实竞赛题
习题 10.4.2
AMC 8Jo 每天在学校都要爬一段 6 级的楼梯。Jo 每次可以爬 1 级、2 级或 3 级。例如，Jo 可以先爬 3 级，再爬 1 级，最后爬 2 级。Jo 有多少种方法爬这段楼梯？
过关检测（第 10.1 节）
3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。10.20%
带限制条件的递推
在本节中，你将能够 处理特殊规则，比如最后一步与众不同，或者有不能踩的台阶。
这次 Jeff 有个奖励：在最后一步，他可以一下跨 3 级！整张表都要变吗，还是只有最上面那个格子变？
只影响最后一步的规则，只会改变最后一个格子。照常填表，然后再看看顶层：最后一步可以从哪些台阶起跳？
递推不只能用来爬楼梯。只要一个大的情况能由更小的情况搭起来，你就可以列一张表。
动手探索先玩，再学公式
认识概念
概念 10.2.1 · 用递推解题
用递推解题，按下面的步骤做：
- 先自己动手算出几个较小的初始值。
- 一般来说，递推式右边有几项，就需要几个初始值。
- 对给定的 ，找出用前面的函数值表示它的递推式。想一想到达那个位置有哪些不同的方式。
- 一个接一个地算出 的值，直到算出你要的那个数。
注 10.2.2
你也可以把 当作初始值。到达第 0 级就是一步也不走，而这样做只有 1 种方法。这样有时会快一点，但也可能让人有点糊涂，所以例题里没有用它。做习题时尽管用！
注 10.2.3
一般来说，多求几个初始值从来没有坏处。如果递推时碰到一个你不确定怎么算的值（比如 或 ），你随时可以回头，再自己动手多算几个初始值。
看例题先预测，再揭晓
例 10.2
Jeff 要爬一段 7 级的楼梯。每一步他都可以爬 1 级或 2 级，但在最后一步，他可以爬 3 级。他有多少种不同的方法爬到顶？
- 1
在最后一步之前，Jeff 每步跨 1 级或 2 级，和例 10.1 一样。所以那里 。 是多少？
先预测一下：
例 10.3
Mike 要爬一段有 10 级的楼梯。他很着急，所以在大部分路程中，他每次爬 2 级或 3 级。如果他到达了第 9 级，就可以再爬 1 级到达第 10 级。Mike 有多少种方法爬到楼梯顶？
- 1
先求初始值。Mike 到达第 1 级有多少种方法？
先预测一下：
自己做
习题 10.4.6（补充题）
Jeff 要爬一段 10 级的楼梯。可是第 3 级和第 9 级上有蜘蛛，他不肯踩这两级台阶。如果他每次可以爬 1 级或 2 级，他有多少种不同的方法爬到顶？
竞赛角真实竞赛题
习题 10.4.3
Omega Learn Math ContestBrandon 想爬到一段 7 级楼梯的顶上。除了最后一跳，每一跳他都可以向前跳 1 级或 3 级。最后一跳，他可以向前跳 1 级、2 级或 3 级。他有多少种不同的方法到达楼梯顶？
习题 10.4.4
AMC 12如果一个整数集合中，任意三个连续整数里至多有一个属于它，就称这个集合是“稀疏的”。 有多少个子集（包括空集）是稀疏的？
过关检测（第 10.2 节）
3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。10.30%
概率递推
在本节中，你将能够 用一张表，一步一步地记录在每个位置上的概率。
一只蟋蟀在 4 片叶子之间跳。每次它都随机跳到另外 3 片叶子中的一片。跳 4 次以后，它最可能在哪里？
跳的次数一多，就没法把每种跳法都列出来了。换个办法：每跳一次，就记录它在每片叶子上的概率。表里的每一新行都由上一行算出来。
注意：蟋蟀总在某一片叶子上，所以每一行加起来都等于 1。
动手探索先玩，再学公式
认识概念
概念 10.3.1 · 概率递推
做概率递推时，一个好办法是直接列一张表，求出每过一个时间步后在每个位置上的概率。记住：每跳一次后，总概率必须始终是 。
看例题先预测，再揭晓
例 10.4
AMC 8一只蟋蟀在 4 片叶子之间随机跳动，每次以相同的概率跳到另外 3 片叶子中的一片。跳了 4 次后，蟋蟀回到出发时那片叶子上的概率是多少？
- 1
把出发的叶子叫作 A。设 是蟋蟀跳了 次后在 A 上的概率，所以 。 是多少？
先预测一下：
过关检测（第 10.3 节）
3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。10.4
练习题
在本节中，你将能够 用递推解决一道很难的竞赛题。
这是一道关于搭塔的 AIME 题。窍门是：一次加一个正方体，让塔慢慢长高，再数一数每个新正方体可以放在哪里。
想在一页里看到本章的所有题目？打开习题集。
竞赛角真实竞赛题
习题 10.4.5
AIME有 8 个正方体，对每个整数 （），都恰好有一个棱长为 的正方体。要用全部 8 个正方体按下面的规则搭一座塔：任何一个正方体都可以放在塔的最底层。紧挨着放在棱长为 的正方体上面的那个正方体，棱长至多为 。一共可以搭出多少座塔？