递推方程的两种特殊解法及其在程序设计中的应用

金渊智

（三门峡职业技术学院信息传媒学院，河南三门峡472000）

0 引言

由于递归具有直观、易理解等特性，因此，在程序设计时，我们经常使用递归来解决某些特定问题。递归[1-3]（Recursion）即某个函数（或功能）一次或多次地在函数体内调用自身来解决相关子问题。当一个问题规模较大时，可以通过递归方法将问题规模逐步减小，最后再合并所有的递归结果，得出整个问题的解。

将函数的递归调用写成方程的形式就是递推方程[4（]Recurrence Equation）。其数学定义是：设序列a0,a1,a2…,an,…,简记为 {an}，一个把an与某些个ai(i＜n)联系起来的等式叫做关于序列 {an}的递推方程。当给定递推方程和适当的初值，就唯一地确定了序列。

在计算机算法分析和程序设计中，使用递归技术往往使得函数的定义和算法的描述非常简洁，通俗易懂，但是有许多问题随着问题规模的增大，计算量呈指数形式增长，那么再高的CPU处理速度，也无法满足人们对算法执行时间的需求。因此在处理实际问题时，通常将时间复杂度为指数级别的算法先求出递推方程的解，再来对算法进行设计、改进和效率评估。

常见递推方程的求解方法有迭代法、尝试法、递归树和主公式法等。本文主要讨论特征方程法和生成函数法，利用Hanoi塔的例子分别验证了这两种方法的正确性。最后利用MATLAB程序测试了Hanoi塔的递归函数运行时间以及求解方程后的程序运行时间。

1 常系数线性递推方程的解法

文献[5]给出常系数线性递推方程的一般定义：

其中a1,a2,…,ak为常数，ak≠0，当f(n)=0称为k阶常系数线性齐次递推方程，b0,b1,b2,…,bk-1为k个初值。当f(n)≠0称为k阶常系数线性非齐次递推方程。

公式（1）的齐次特征方程为

该特征方程的根就是原递推方程的特征根，根据方程阶的不同，公式（2）可能多重根，利用多重根来构造通解的线性组合，然后再根据初值列出方程组，求出待定常数。如果构造的线性组合有两个或多个线性相关的话，就无法求出待定系数。对于非齐次的情况可以通过先求齐次通解再加上一个非齐特解来构造。

Hanoi塔的递推方程如下

根据定义这是一个非齐次方程，其齐次特征方程为：x-2=0，即x=2，因此构造线性无关的通解是c2n，设P为原方程的特解，代入原方程得

即P=-1，再加上齐次通解既是公式（3）的解

再代入初值T(1)=1，得c=1，最终公式（3）的解

2 利用生成函数求解递推方程

生成函数[6]也可以用于求解递推方程。一个序列对应一个生成函数，同时一个序列可以满足某个递推关系，因此，可以将递推关系表示成生成函数，然后在利用生成函数与幂级数的关系来求解递推方程。对于公式（3）Hanoi塔的例子使用生成函数求解的过程如下：

1）先计算生成函数

整理得

2）用生成函数表达递推序列

与前述方法求解结果一致。

3 求解递推方程对于程序设计的意义

如果要编写计算Hanoi塔盘子的移动次数的程序，最简单的就是使用递推公式编写递归函数，

其中xn项的系数就是递推方程的解，即其MATLAB程序代码如下：

随着问题规模n（盘子个数）的增加，这个递归函数的计算量程指数级增长，这是我们无法接受的。印度僧侣预测，将64盘子转移完毕，就是世界末日。可见当n=64时问题的规模已经相当大了。那么，利用公式（8）递推方程的求解结果，我们很容易计算盘子的移动次数，其MATLAB的程序代码如下：

为了程序计时，引入t0和t1变量。为了对比递归程序和求解递推方程后的程序效率，对不同大小的n做了实验，数据如表1所示。

表1 递归程序与求解方程后的程序运行时间对比

其中的“0”表示时间太短，MATLAB系统无法计时，“-”表示时间过长，大于100分钟。由此可以看出，当n=25两种方法的求解用时已经差距非常大了；当n=35时，递归算法用时已经接近80分钟；当n=40时，实验用的计算机已经无法快速计算递归算法了。求解递归方程后的程序运行时间几乎全部为“0”秒，当n=64时，若采用配置较高的计算机，程序用时也是“0”秒。

4 结束语

由于递推方程的类型较多，求解的方法很难统一，因此对于递推方程解法的研究从未停止。本文讨论了两种特殊的递推方程解法，对于非数学领域，特别是计算机程序员有一定的参考价值。最后通过MATLAB实例仿真对比，论证了求解递推方程的必要性和现实意义。因此，在程序设计时尽量避免使用递归算法，可以先将递归算法利用求解递推方程转化为非递归算法，再编写程序代码，以提高程序的执行效率。