设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i
定义
设是一个序列。如果和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。
如：设是一个序列，把该序列中的a和它前面的几个和错排数:，都是递归关系。
有时也称递归关系式为差分方程。为了能从递归关系式计算出序列的每一项，必须知道序列开始的一个或几个数，称这样的数为初始条件(initial condition)或初始值。
在许多情况下，得到递归关系式本身就是朝解决一个计数问题迈了一大步。即使不能从这个递归关系式很快地解出它的一般表达式，这也是相当不错的了。这是因为采取逐步计算的方法可以得到序列各项的值。有些例子说明，没有递归关系，计算的可能性根本就不存在。
递归关系模型
斐波那契序列
首先比较详细地研究一个特殊的计数序列。这个序列是通过递归关系定义的。Pisa的Leonardo在1202年出版的名为“Liber Abacci(关于算盘)”一书中，提出了一个问题。该问题是如何确定一对兔子在一年里生产多少对兔子?Leonardo，因Fibonacci(Filius Bonacci的缩写)这个名字而更为人们所知道。
由Fibonacci提出的问题是，在一年的开始，将一对兔子放进围场中。每个月，一对兔子中的雌性兔子生下新的雌雄各异的一对兔子。每对新兔子从第二个月起也是每月生产一对兔子。求一年后，围场内兔子的总对数。
在第一个月内，所给定的一对兔子将生产一对新兔子，所以，在第一个月末，围场中，将有两对兔子。在第2个月内，唯有最初的一对兔子生产一对兔子，所以，在第2个月末，围场中，将有3对兔子。在第3个月内，最初的一对兔子以及在第一个月所生产一对兔子都将各自生产一对兔子，所以，在第3个月末，围场中，将有对兔子。对每个，令f(n)表示第n月初（等价地讲，第月末）围场中的兔子对的总数。有，而要计算的是f(13)。以下将f(n)的递归关系着手，可以容易地计算出f(13)。在围场中的第月初的兔子对仍将在第n月初存在；另外，在第月初的就已存在的所有兔子对在第月内各生产一对新的兔子，于是在第n月初有对兔子，所以对有
利用这个关系和已经计算出的f(1)，f(2)，f(3)，f(4)值，可以得到
于是，一年后，围城内有377对兔子。
如果令，于是.数序列f(0)，f(1)，f(2)，…满足递归关系：对于有连同初始值被称为斐波那契序列，并且称序列中的数为斐波那契数。通过计算知道该序列是：
1，1，2，3，5，8，13，21，34，55，89，144，233，377，…
斐波那契序列有许多值得注意的性质。例如，斐波那契序列f(0)，f(1)，f(2)，…项的部分求和具有
对于，该公式简化为，由于，所以显然公式是成立的。
假设结论对任意的自然数时成立，则时，
由数学归纳法原理，得到证明。
现在需要做的事情是找出一个显式表示斐波那契数。考虑斐波那契的对于递归关系，并略去f(0)和f(1)值。解决这个递归关系的一种方法是寻找形式为的一个解。它的第一项是。发现：满足斐波那契递归关系当且仅当，或对于有。因为假设，所以得到是斐波那契递归关系的一个解当且仅当，或等价地讲，当且仅当q是二次方程的一个根。该方程的根是
于是
是斐波那契递归函数的两个解。由于这个递归关系式线性的（没有f的不是1的方幂）齐次的（没有常数项），所以导出
对于任意的常数和，是递归函数的解。
因为斐波那契序列有初始值，所以可以通过二元一次方程组来确定常数和。
时，得：
时，得：
解得：
概括起来，有以下定理
1.斐波那契数满足公式
对
对于不同的处置，c和c将得到不同的值，f(n)的形式也有所不同。
2.沿着杨辉三角或Pascal三角形的对角线，从左向上的二项式系数之和等于斐波那契数。更确切地说，对于，第n斐波那契数f(n)满足
其中
河内塔
递归关系的另外一个很重要的模型是河内(Hanoi)塔。如下图所示，1，2和3是三根直立的杆子．不妨设，开始时有n个圆盘依大小，自下而上套在杆1上，并且n个圆盘的半径两两不同。现在按照三条规则，将杆1上的圆盘以原样全部转移到杆2或杆3上。这三条规则是：(1)每次只转移一个圆盘；(2)整个转移过程始终保持较小的在较大的上面的形式；(3)有而且仅有三根立杆1，2和3供使用。
问：最少要移动多少次，才能将杆1上的n个圆盘以原样全部转移到杆2或杆3上?
稍加分析不难看出，按照上述三条转移规则，n个圆盘的转移只能按下面的过程进行：第一步将杆1最上面的个圆盘，借助杆2或杆3转移到其中的一根上，不妨设转移到杆2上。第二步将杆1的最下面的大圆盘转移到杆3上．第三步借助杆1和杆3，再把杆2上的n-1个圆盘转移到那个套有最大圆盘的立杆3上，如下图所示。
假设h表示转移n个圆盘所需要的最少移动次数，那么执行第一步需要h次，执行第二步需要一次，执行第三步需要h次，于是最少移动的总次数等于
并且初始条件。显然，的表达式也是一个递归关系式。
应用
在平面上有n条直线，假定没有两条直线是平行的，且没有三条直线是共点的，问这个平面被这n条直线分隔成多少个区域?
解：令a表示n条直线将平面分割成的区域数。显然，当时，由下图可得，。
现在假定平面上已有n-1条直线把平面分割成a个区域，再在平面上插入第n条直线。它与原条直线相交，得到个不同的交点，这个点把第n条直线分成n段，从而产生了n个新区域。例如在上图的(3)中平面省上三条直线将平面分割成7个区域，现加进第4条直线，与原三条直线相交，得3个交点，产生了4个新区域，如下图阴影部分。因此，我们推知有如下的递归关系：
而
参考资料 >