递推方法与解题之道（2015.4南安一中—陈俊鸿）

递推方法与解题之道

1 什么是递推法

如果数列{an}的第n项与它前一项或多项的关系可以用一个式子（等式或不等式）来表示，那么这个式子叫做这个数列的递推公式．通过建立递推公式解决问题的方法称之为递推法．

递推法是探索数学规律和解题思路的重要方法之一，它对几乎所有的数学分支都有着重要的作用．随着计算机的广泛应用，这种方法越来越受到重视．

例如：数列{an}的首项a1?1，从第二项起每一项等于它的前一项的2倍再加1，即：

?1an???2an?1?12 递推关系的建立

n?1n?1且n?N①②

其中①为初值，②为递推公式，①②合起来称为带初值的递推公式，也称递推式．

下面用一个例子简要介绍一下怎样建立递推关系．

例1：某人想登一10阶的楼梯，每步只能登1阶或者2阶，问刚好走到第10阶共有多少种不同的走法？

解法一：组合计数分类讨论．

由于每步只能登1阶或者2阶，所以一共可以分成以下几种情况： ① 走0步2阶的，此时即全部走1阶的，共1种走法；

② 走1步2阶的，即此时只需要走9步，其中有1步是走2阶的，只需考虑哪一步是走2阶

1的就可以了，共C9种

③ 走2步2阶的，即此时只需要走8步，其中有2步是走2阶的，只需考虑哪2步是走2阶的就可以了，共C82种；

3同理可得：④ 走3步2阶的，共C7种；

4⑤ 走4步2阶的，共C6种； 5⑥ 走5步2阶的，共C5种．

01345根据加法原理，可知答案为C10+C9+C82+C7+C6+C5=89种走法．

解法二：递推法．

我们发现，如果要走到第n阶，由于最多只能走两阶，所以走到第n阶只能有两种情况：

1

① 从第n?1阶向上登1步1阶到达第n阶； ② 从第n?2阶向上登1步2阶到达第n阶． 于是，我们设f(n)表示走到第n阶的方法总数，f(n)可以分成两类：

① 在第n?1阶，向上登1步1阶到达第n阶，此时的走法总数即为到达第n?1阶的走法总数，即有f(n?1)种；

② 在第n?2阶，向上登1步2阶走到第n阶，此时共有f(n?2)种．

根据加法原理，可得f(n)?f(n?1)?f(n?2)．对于初值，显然f(1)?1,f(2)?2，所以我们便得到了f(n)的递推式（即著名的斐波那契数列递推式）：

?1?f(n)??2?f(n?1)?f(n?2)?n?1n?2n?2且n?N

由递推式，我们可以计算得：

n f(n) 1 1 2 2 3 3 4 5 5 8 6 13 7 21 8 34 9 55 10 89 所以，例1答案共有f(10)?89种走法．

利用递推法，本例很容易扩展到n阶楼梯的一般情形．特别的，如果题目改成每步可以登1阶、2阶和3阶，同理可得递推式f(n)?f(n?1)?f(n?2)?f(n?3)，f(1)?1，f(2)?2，

f(3)?4，此时递推法的优势会得到更大的体现??

用递推法解决计数问题的一般步骤为：

① 将欲计数的对象一般化，并用f(n)表示与n有关的欲计数的对象个数； ② 计算一些初始值f(1),f(2),③ 建立f(n)与f(n?1),f(n?2),,f(k)；

,f(n?k)之间的递推公式；

④ 用初始值与递推公式依次计算出f(k?1),f(k?2),知识推导出f(n)的通项公式，并求f(n0)的值）． 3 递推法在组合计数问题中的应用

,f(n0)的值（有时候也可以利用数列

上面介绍了递推关系的建立，下面主要以计数问题为例，通过一些具体的例子来分析、比较并体会递推法的优势．

2

3.1 一维形式的递推法

例2：如图1，一环形花坛被分成A,B,C,D,E五个区域，现有5种不同的花可供选种，要求在每个区域里种1种花，且相邻的2个区域种不同的花，则不同种法的总数为___________．（改编自2008高考全国卷1理科第12题，原题是4种花4个区域）．

解法一：分类分步计数；

考虑按A,B,C,D,E的顺序进行分步计算：

（1）C与A种的花相同，此时A,D,E种的花互不相同，共5?4?1?4?3=240种；

（2）C与A种的花不同，此时A,B,C种的花互不相同，A,B,C共5?4?3种，而D种的花是

否与A相同会影响到E的选择种数，因此，在（2）的条件下，对D再次分类： ① D与A种的花相同，此时D有1种选择，E有4种选择，共5?4?3?1?4=240种； ② D与A种的花不同，此时A,D,E种的花互不相同，且D与C种的花不同，故D有3种选择，E有3种选择，共5?4?3?3?3=540种； 根据加法原理，共有240+240+540=1020种种法；

点评：解法一太过繁琐且容易出现重复计数或遗漏．我们是否可以像例1一样用递推法呢？答案是肯定的，下面我们来看看递推法． 解法二：递推法

为简化问题，我们不妨将环形沿A,E相邻线“剪”开拉直，形成一个长条形．则原问题转化为在如图2分成A,B,C,D,E5块区域的长条形中种5种不同颜色的花，要求相邻的两块区域不同色且第一块和最后一块区域也不同色的种法总数．

AED图1BCAED图1BCABC图2DE

如图3，我们设f(n)表示在被分成A1,A2,A3,

3

,An?2,An?1,An共n个区域的长条形中种5种

不同颜色的花，要求相邻的两块区域不同色且第1块区域和第块n区域也不同色的种法总数．

A1A2A3…An-2An-1An图3

由于An与A1不同色，于是我们可以分成两种情况：

① An?1与A1不同色，此时An与An?1、A1均不同色，有3种选择．由于An?1与A1不同色，所以我们可以把An?1和A1 “接”起来，变成环形，并且满足任意相邻区域不同色，而这个n?1个区域的环形共有f(n?1)种符合条件的种花方案．根据乘法原理，此时共有3f(n?1)种方案； ② An?1与A1同色，此时An有4种选择．由于An?1与A1同色，且An?1与An?2不同色，所以An?2与A1不同色，此时An?1与A1同色的n?1个区域的长条形的种法方案总数即An?2与A1不同色的

n?2个区域的方案总数．同理，n?2个区域的环形共有f(n?2)种符合条件的种花方案，根

据乘法原理，共有4f(n?2)种方案． 根据加法原理，f(n)?3f(n?1)?4f(n?2)，

?5?5?4? f(n)???5?4?3??3f(n?1)?4f(n?2)n?1n?2n?3n?3且n?N

思考：为何f(3)要独立出来，难道不能用f(3)?3f(2)?4f(1)求得吗？①（答案见后） 根据递推式，可知：f(2)?20,f(3)?60，f(4)?3f(3)?4f(2)?180?80?260

f(5)?3f(4)?4f(3)?780?240?1020

所以共有1020种符合的种法． 拓展：

如果要求放6种花，7种花，8种花，甚至更多的花怎么办？

很简单，假设要在n个区域中种m种花，只要对原先的递推式稍微修改下即可． 即：

?m?m(m?1)?f(n)???m(m?1)(m?2)??(m?2)f(n?1)?(m?1)f(n?2)

n?1n?2n?3n?3且n?N4

于是我们有了n个区域中种m种不同的花，要求相邻区域种的花不同且首尾不同的种法总数的模型了．2003年全国高考，2003年天津理科高考，2001年全国高中数学联赛等里面都有题目可以用该模型去解决．

例3：有4位老师在同一年级的4个班级中，各教一个班的数学，在数学考试时，要求每位老师均不在本班监考，则安排监考的方法总数是___________． 解法一：穷举法

44个老师4个班级，共有A4=24种监考情况，列出所有情况把所有符合的筛选出来即可．答5案为9种．但是如果题目改成5个老师5个班级呢？穷举？A5=120！！不太现实．试试递推

法看看． 解法二：递推法

设f(n)表示有n个老师，监考n个教室，且各个老师都不监考自己的教室的方案总数．

1于是在n个老师中，恰好只有1个老师监考自己的教室的情况有Cnf(n?1)种；

2恰好只有2个老师监考自己的教室的情况有Cnf(n?2)种；

??

k恰好只有k个老师监考自己的教室的情况有Cnf(n?k)种；

n又n个老师监考n个教室的所有情况有An种，总数减去这些不符合要求的即为答案，即

nkf(n)?n!??Cnf(n?k)，好复杂的递推公式，难道只能另辟奇径了？

k?1解法三：还是递推法

我们换个角度，还是设f(n)表示有n个老师，监考n个教室，且各个老师都不监考自己的教室的方案总数．显然，第n个老师只能监考1,2,,n?1这n?1个教室之一，不妨设第n个

老师监考了第k个教室，1?k?n?1，那么就可以分成两种情况了：

① 第k个老师去监考第n个教室．此时第n个老师和第k个老师的教室对换，其余还剩n?2 个老师和n?2个教室，且每个老师都不能监考自己的教室，即有f(n?2)种情况； ② 第k个老师不去监考第n个教室．这种情况下，1,2,1,2,,k?1,k?1,,n?1,n这n?1个教室和

,n?1这n?1个老师中，除了第k个老师每个老师都不能监考自己的教室，而第k个老师

不监考第n个教室，此时相当于可以把第n个教室看成是第k个老师的教室，那么方案总数就

5

本文来源：https://www.bwwdw.com/article/k4sv.html