7-6-4.计数之递推法
前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用．
教学目标
对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法． 【例 1】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔
子来．如果一个人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？
【考点】计数之递推法 【难度】3星 【题型】解答 【解析】 第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大
兔子生下一对小兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加． 依次类推可以列出下表：
经过月数：---1---2---3---4---5---6---7---8---9---10---11---12
兔子对数：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月
份的时候总共有144对兔子． 【答案】144
【例 2】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才
能萌发新枝．一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？
【考点】计数之递推法 【难度】3星 【题型】解答 【解析】 一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，
55，89，……所以十年后树上有89条树枝．
【答案】89
【例 3】 一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不
同走法？
【考点】计数之递推法 【难度】4星 【题型】解答
例题精讲
7-6-4.计数之递推法.题库 教师版 page 1 of 9
【解析】 登 1级 2级 3级 4
级 ...... 10级
1种方法 2种 3种 5
种 ...... ？
我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做A0，那么登了1级的位置是在A1，2级在A2... A10级就在A10．到A3的前一步有两个位置；分别是A2 和A1 ．在这里要强调一点，那么A2 到A3 既然是一步到了，那么A2 、A3之间就是一种选择了；同理A1 到A3 也是一种选择了．同时我们假设到n级的选择数就是An ．那么从A0 到A3 就可以分成两类了：第一类：A0 ---- A1 ------ A3 ，那么就可以分成两步．有A1×1种，也就是A1 种；(A1 ------ A3 是一种选择)第二类：A0 ---- A2 ------ A3， 同样道理 有A2 ．类类相加原理：A3 = A1 ＋A2，依次类推An = An-1 + An-2． 【答案】89
【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 登 1级 2级 3级 4级 5
级 ...... 10级
1种方法 1种 2种 3种 4
种...... ？
我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28. 【答案】28
【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法． 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 如果用1?2的长方形盖2?n的长方形，设种数为an,则a1?1，a2?2,对于n?3，
7-6-4.计数之递推法.题库 教师版 page 2 of 9
左边可能竖放1个1?2的，也可能横放2个1?2的，前者有an-1种，后者有an-2种，所以an?an-1?an-2,所以根据递推，覆盖2?10的长方形一共有89种．
【答案】89
【例 5】 用1?3的小长方形覆盖3?8的方格网，共有多少种不同的盖法？ 【考点】计数之递推法 【难度】5星 【题型】解答 【解析】 如果用1?3的长方形盖3?n的长方形，设种数为an,则a1?1，a2?1,a3?2,对于
n?4，左边可能竖放1个1?3的，也可能横放3个1?3的，前者有an-1种，后者
有an-3种，所以an?an-1?an-3,依照这条递推公式列表：
3?1 3?2 3?3 3?4 3?5 3?6 3?7 3?8 1 1 2 3 4 6 9 13 所以用1?3的小长方形形覆盖3?8的方格网，共有13种不同的盖法． 【答案】13
【例 6】 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不
同取法？
【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取
任意根火柴的种数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如下： 1根 2根 3根 4根 5根 6根 7根 8根 9根 10根 11根 12根 1 2 4 7 13 24 44 81 149 274 504 927 取完这堆火柴一共有927种方法． 【答案】927
【巩固】 一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同
取法？
【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取
任意个苹果的种数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下： 1个 2个 3个 4个 5个 6个 7个 8个 1 2 4 7 13 24 44 81 取完这堆苹果一共有81种方法． 【答案】81
【例 7】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不
同的拿法？
【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举． (法1)递推法．假设有n枚棋子，每次拿出2枚或3枚，将n枚棋子全部拿完的拿法总数为an种．
则a2?1，a3?1，a4?1．
由于每次拿出2枚或3枚，所以an?an?3?an?2(n?5)．
所以，a5?a2?a3?2；a6?a3?a4?2；a7?a4?a5?3；a8?a5?a6?4；a9?a6?a7?5；a10?a7?a8?7．
即当有10枚棋子时，共有7种不同的拿法． (法2)分类讨论．
7-6-4.计数之递推法.题库 教师版 page 3 of 9