张淑云
湖南省冷水江市铎山镇中心小学 417508
摘 要：计数问题是学习和生活中经常遇到的一类问题，它的表现形式多样,处理方法灵活,其中递推法是处理复杂计数问题的一种重要方法。本文通过几个典型例子，说明递推法在解计数问题中的应用。
关键词：计数问题，递推法，例析
意大利著名数学家斐波那契（约1170—1250）有一部传世之作《算术之法》，其中提出了一个饶有趣味的问题：假定一对刚出生的兔子一个月就能长成大兔子，再过一个月就开始生下一对小兔子，并且以后每个月都生一对小兔子。设所生一对兔子为一雌一雄，且均无死亡。问一对刚出生的小兔一年内可以繁殖成多少对兔子？
对于斐波那契提出的这个“兔子繁殖问题”，我们不妨一个月一个月向后推算：
开始时有一对小兔，即a0=1；第1个月，这对小兔长成一对大兔，即a1=1；第2个月，这对大兔产下一对小兔，此时共有两对兔子，即a2=2；第3个月，原来的大兔产下一对小兔，第2个月出生的一对小兔长成大兔，即a3=3；第4个月，原来的和第2个月出生的兔子各产下一对小兔，而第3个月出生的一对小兔长成大兔，此时共有5对兔子，即a4=5；……
如果按照上述“连锁反应”式地繁殖小兔，来推算出一年（12个月）内可以繁殖成多少对兔子，我们确实要费一番功夫。因此，我们需要找出一个简捷的“连锁反应关系式”来解出a12。
设第n个月共有an对兔子，则an是由两部分构成的，其中一部分是第（n-1）个月的兔子对数an-1；第二部分是由an-2对兔子所生的小兔，共有an-2对。所以an=an-1+ an-2。
由于a0=1，a1=1，因此每个月的兔子对数依次为：
1，1，2，3，5，8，13，21，34，55，89，144，233，…。
这里可以看出a12=233，即一对刚出生的小兔一年内可以繁殖成233对兔子。
我们将会在许多场合，甚至在中小学数学教材中经常遇到上面这列数，它被称为“斐波那契数列”。它的前两项是1，从第3项开始，任一项都是前两项的和，即有关系式an=an-1+ an-2(n=2，3，…)。
像这种利用“连锁反应”的关系而得到的关系式，称为递归关系，有了递归关系就可以利用前面的数求出后面的未知数。上述例子中，通过寻找递归关系解题的方法称为递推法。递推法是解决复杂计数问题的一种重要方法，它比列表法计数简洁，比对比法计数更具操作性。下面举例说明递推法在计数解题中的应用，例子着重说明如何建立递归关系，并利用递归关系进行计数。
例1 将2×10的棋盘每一格编上号（如图1），用10张1×2的长方形卡片去覆盖棋盘，有多少方法把棋盘完全盖住？
分析与解 对于2×n的棋盘，用n张1×2的长方形卡片去覆盖棋盘，有Fn种方法把棋盘盖住。1号格盖住有两种情形：一类是1号与2号同时被一张1×2的卡片盖住，剩下的2×（n－1）的棋盘有Fn-1种方法盖住；另一类是1号与3号同时被一张1×2的卡片盖住，这时2号与4号也必被一张卡片盖住，剩下的2×（n－2）的棋盘有Fn-2种方法盖住。由加法原理，知Fn＝Fn-1＋Fn-2。由于F1＝1，F2＝2，F3＝3，利用递归关系Fn＝Fn-1＋Fn-2，做一些简单的加法运算，就可得到F10＝89。
所以，共有89种方法把2×10的棋盘完全盖住。
例2 一栋高楼的楼层之间总是有楼梯相连，每层楼梯一般有20级台阶，规定每一步只能跨一级或两级，从一层楼登上上一层楼有多少种不同走法？
分析与解 由于登台阶每次只能跨一级或两级，因此登上第n级台阶的情形仅与登上第（n-1）级台阶和第（n-2）级台阶有关。可以考虑建立递归关系，把登上第n级台阶的走法分为两类：一类是已登上第（n-1）级台阶再跨上一步，这有an-1种走法；另一类是已登上第（n-2）级台阶，再跨上两级台阶，这有an-2种走法。根据加法原理，有an=an-1+an-2。
推算几种简单情形：a1=1，a2=2，a3=3，利用递归关系an=an-1+an-2递推，得a20=10946。
即从一层楼登上上一层楼有10946种不同走法。
例3 圆周上两个点将圆周分为两半，在这两个点上写上数1；然后将两段半圆弧等分，在这两个分点上写上相邻两点上的数之和；再把4段圆弧等分，在分点上写上相邻两点上的数之和。如此继续下去，第8步后，圆周上所有点上的数之和是多少？
分析与解 如图2，第一步有两个点，第二步有四个点，第三步有八个点。每一步将前一步所得的圆周再细分一次，所以每一步后所有点的个数是前一步后点的个数的两倍。
那么每一步添加的点上的数有什么规律呢？
可能你会认为第n步增加的数都是n，因为第一步增加的是1，第二步增加的是2，第三步增加的是3。事实上并不是这么回事。比如在第四步时，增加的数除了4以外还有5（图2）。可见我们必须另行找出正确的规律。
因为问题是求出圆周上所有数的和，我们不必去考虑每步具体增加了哪些数，只需关心每一步增加的数的总和是多少。明确了这一点，事情就好办多了。因为增加的每个数都是原来相邻两个数之和，所以增加数之和恰好是原来所有数之和的两倍，也就是说，圆周上所有数之和是前一步后圆周上所有数之和的3倍。设an为第n步后得出的圆周上所有数之和，则得递归关系an=3×an-1。
利用上式递推可以得到：
。
因为a1=2，所以。
取n=8，有a8=4374。即第8步后圆周上所有点上的数之和为4374。
例4 在平面上画2020条直线，这些直线最多能把平面分成多少块？
分析与解 显然，要想平面分得的块数最多，画出的直线应满足如下两个条件：
（1）任何两条直线不能平行；
（2）任何三条直线不能交于同一点。
先画几个简单图形（图4），数出相应的块数来寻找规律。
从中可以看出：第n条直线和前n-1条直线相交，增加n-1个交点，这些交点把第n条直线分成n段，新增加n块区域。设直线把平面分成的块数为fn，则得递归关系式：fn＝fn-1＋n。利用这个关系递推，得
fn＝fn-1＋n＝fn-2＋（n-1）＋n＝fn-3＋（n-3）＋（n-1）＋n
＝…＝f1＋2＋3＋4＋…＋（n-1）＋n。
由f1＝1，得fn＝2＋2＋3＋4＋…＋（n-1）＋n＝。
故f2020＝2＋2＋3＋4＋…＋2020＝1＋＝2041211。
即在平面上画2020条直线最多能把平面分成2041211块。
例5 印度有这样一个古老的传说：
在佛教圣地贝那勒斯的一个寺庙里有一块黄铜板，板上插着三根宝石针，第一根针上套着64块大小不等的金片（大的在下面，小的在上面）。传说这是开天辟地的神勃拉玛在创造世界时留在那里的。不论白天黑夜，寺内都有一个僧人按照如下的法则移动金片：把第一根针上的金片移到第三根上去，而一次仅能移动一块，且在每次移动过程中不能将大金片置在小金片的上面。第二根针可以作辅助过渡用。神预言，当这64块金片都移到第三根针上时，世界末日就来临了，世间的一切终将毁灭，万物都将至极乐世界。请问：世界末日何时来临？
分析与解 这个著名的“世界末日问题”，在人教版小学数学四年级上册教材安排了一道把它经过简化的题目。我们先简单情形开始思考，去探究其中的规律。
（1）如果第一根针上只有1块金片，把金片移到第三根针上只需要移1次；
（2）如果第一根针上有2块金片，先把小金片移到第二根针上，再把大金片移到第三根针上，再把小金片移到第三根针上，总共需要移3次；
（3）如果第一根针上有3块金片，先把上面的2块金片移到第二根针上，需要移3次；再把最下面的1块大金片移到第三根针上需要移1次；最后把第二根针上的2块金片移到第三根针上又需要移3次。总共需要移3＋1＋3＝7次；
（4）如果第一根针上有4块金片，先把上面的3个金片移到第二根针上，需要移7次；再把最下面的1块大金片移到第三根针上需要移1次；最后把第二根针上的3块金片移到第三根针上又需要移7次。总共需要移7＋1＋7＝15次。
至此，我们得到一个数列：1，3，7，15，…。这个数列的规律是：数列的后一项总是比前一项的2倍多1。
如果把第一根针上的n片金片全部移到第三根针上所需最少次数为an，那么an＝2an-1+1。利用这个关系可以得到：
。
因为a1＝1,所以。
当n＝64时，就有a64＝264－1。
根据以上的计算，当所谓“世界末日”来临时，金片将被移动（264－1）次，这是一个惊人的天文数字。如果按一年为365天计算，一个人不吃饭也不睡觉，日夜不停地移动金片，一秒钟移动一片，大约要5849亿年。根据科学家的研究，地球的“寿命”不多于200亿年，那么，不等僧人移完那金片，地球早就“寿终正寝”了。
参考文献：
[1]肖乐农. 投石问路[J]. 小学教学参考，?2006（Z5）：79-80.
[2]马 杰. 构造递推公式解计数问题[J].中学生数学，2020（21）：32-33.