递归关系

数学术语

设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i

定义

设p0，p1，…，pn，…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。

如：设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤ir=3ar-1 (r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，都是递归关系。

有时也称递归关系式为差分方程。为了能从递归关系式计算出序列的每一项，必须知道序列开始的一个或几个数，称这样的数为初始条件(initial condition)或初始值。

在许多情况下，得到递归关系式本身就是朝解决一个计数问题迈了一大步。即使不能从这个递归关系式很快地解出它的一般表达式，这也是相当不错的了。这是因为采取逐步计算的方法可以得到序列各项的值。有些例子说明，没有递归关系，计算的可能性根本就不存在。

递归关系模型

递归关系有两个比较著名的模型是：斐波那契序列和河内塔。

斐波那契序列

首先比较详细地研究一个特殊的计数序列。这个序列是通过递归关系定义的。Pisa的Leonardo在1202年出版的名为“Liber Abacci(关于算盘)”一书中，提出了一个问题。该问题是如何确定一对兔子在一年里生产多少对兔子?Leonardo，因Fibonacci(Filius Bonacci的缩写)这个名字而更为人们所知道。

由Fibonacci提出的问题是，在一年的开始，将一对兔子放进围场中。每个月，一对兔子中的雌性兔子生下新的雌雄各异的一对兔子。每对新兔子从第二个月起也是每月生产一对兔子。求一年后，围场内兔子的总对数。

在第一个月内，所给定的一对兔子将生产一对新兔子，所以，在第一个月末，围场中，将有两对兔子。在第2个月内，唯有最初的一对兔子生产一对兔子，所以，在第2个月末，围场中，将有3对兔子。在第3个月内，最初的一对兔子以及在第一个月所生产一对兔子都将各自生产一对兔子，所以，在第3个月末，围场中，将有2+3=5对兔子。对每个n=1，2，3，…，令f(n)表示第n月初（等价地讲，第n-1月末）围场中的兔子对的总数。有f(1)=1，f(2)=2，f(3)=3，f(4)=5，而要计算的是f(13)。以下将f(n)的递归关系着手，可以容易地计算出f(13)。在围场中的第n-1月初的兔子对仍将在第n月初存在；另外，在第n-2月初的就已存在的所有兔子对在第n-1月内各生产一对新的兔子，于是在第n月初有f(n-1)+f(n一2)对兔子，所以对n=3，4，…有

利用这个关系和已经计算出的f(1)，f(2)，f(3)，f(4)值，可以得到

于是，一年后，围城内有377对兔子。

如果令f(0)=1，于是f(2)=2=1+1=f(1)+f(0).数序列f(0)，f(1)，f(2)，…满足递归关系：对于n=2，3，4，…有连同初始值f(0)=1和f(1)=1被称为斐波那契序列，并且称序列中的数为斐波那契数。通过计算知道该序列是：

1，1，2，3，5，8，13，21，34，55，89，144，233，377，…

斐波那契序列有许多值得注意的性质。例如，斐波那契序列f(0)，f(1)，f(2)，…项的部分求和具有

对于n=0，该公式简化为f(0)=f(2)一1，由于1=2-1，所以显然公式是成立的。

假设结论对任意的自然数k(>o)，n=k--1时成立，则n=k时，

由数学归纳法原理，得到证明。

需要做的事情是找出一个显式表示斐波那契数。考虑斐波那契的对于n=2，3，4，…递归关系，并略去f(0)和f(1)值。解决这个递归关系的一种方法是寻找形式为f(n)=qn的一个解。它的第一项是q0=1。发现：f(n)=qn满足斐波那契递归关系当且仅当qn=qn-1+qn-2，或对于n=2，3，4，…有qn-2(q2-q-1)=0。因为假设q≠0，所以得到f(n)=qn是斐波那契递归关系的一个解当且仅当q2-q-1=0，或等价地讲，当且仅当q是二次方程x2-x-1=0的一个根。该方程的根是

于是

是斐波那契递归函数的两个解。由于这个递归关系式线性的（没有f的不是1的方幂）齐次的（没有常数项），所以导出

对于任意的常数c1和c2，是递归函数的解。

因为斐波那契序列有初始值f(0)=f(1)=1，所以可以通过二元一次方程组来确定常数c1和c2。

n=0时，得：c1+c2=1

n=1时，得：

解得：

概括起来，有以下定理

1.斐波那契数满足公式

对n=0,1,2，...

对于不同的处置，c1和c2将得到不同的值，f(n)的形式也有所不同。

2.沿着杨辉三角或Pascal三角形的对角线，从左向上的二项式系数之和等于斐波那契数。更确切地说，对于n≥0，第n斐波那契数f(n)满足

其中 .

河内塔

递归关系的另外一个很重要的模型是河内(Hanoi)塔。如图1所示，1，2和3是三根直立的杆子．不妨设，开始时有n个圆盘依大小，自下而上套在杆1上，并且n个圆盘的半径两两不同。按照三条规则，将杆1上的圆盘以原样全部转移到杆2或杆3上。这三条规则是：(1)每次只转移一个圆盘；(2)整个转移过程始终保持较小的在较大的上面的形式；(3)有而且仅有三根立杆1，2和3供使用。

问：最少要移动多少次，才能将杆1上的n个圆盘以原样全部转移到杆2或杆3上?

稍加分析不难看出，按照上述三条转移规则，n个圆盘的转移只能按下面的过程进行：第一步将杆1最上面的n-1个圆盘，借助杆2或杆3转移到其中的一根上，不妨设转移到杆2上。第二步将杆1的最下面的大圆盘转移到杆3上．第三步借助杆1和杆3，再把杆2上的n-1个圆盘转移到那个套有最大圆盘的立杆3上，如图2所示。

假设hn表示转移n个圆盘所需要的最少移动次数，那么执行第一步需要hn-1次，执行第二步需要一次，执行第三步需要hn-1次，于是最少移动的总次数等于

并且初始条件h1=1。显然，hn的表达式也是一个递归关系式。

应用

在平面上有n条直线，假定没有两条直线是平行的，且没有三条直线是共点的，问这个平面被这n条直线分隔成多少个区域?

解：令an表示n条直线将平面分割成的区域数。显然a0=1，当n=1，2，3时，由图3可得，a1=2，a2=4，a3=7。

假定平面上已有n-1条直线把平面分割成an-1个区域，再在平面上插入第n条直线。它与原n-1条直线相交，得到n-1个不同的交点，这n-1个点把第n条直线分成n段，从而产生了n个新区域。例如在图3的(3)中平面省上三条直线将平面分割成7个区域，现加进第4条直线，与原三条直线相交，得3个交点，产生了4个新区域，如图4阴影部分。因此，我们推知有如下的递归关系：

而a0=1.

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省