递归方程求解方法综述

摘 要 ：随着计算机科学的逐步发展,各种各样的算法相继出现,我们需要对算法进行分析,以选择性能更好的解决方案.算法分析中计算复杂度常用递归方程来表达,因此递归方程的求解有助于分析算法设计的好坏.阐述了常用的3种求解递归方程的方法：递推法、特征方程法和生成函数法.这3种方法基本上可以解决一般规模递归方程的求解问题.

关 键 词 ：递归；递推法；特征方程；生成函数

中图分类号：TP301文献标识码：A文章编号：16727800（2011）012003902

作者简介：郭萌萌(1983- ),女,山东济南人,硕士,山东英才学院计算机电子信息工程学院讲师,研究方向为软件工程、算法分析与设计.

0引言

寻求好的解决方案是算法分析的主要目的,问题的解决方案可能不只一个,好的方案应该执行时间最短,同时占有存储空间最小,故算法分析一般考虑时间复杂性、空间复杂性两方面的参数.在算法分析时我们采用时间耗费函数来表示时间参数,用当问题规模充分大时的时间耗费函数的极限表示时间复杂度.

一般算法对应的时间耗费函数常用递归方程表示,找出递归方程的解,就可以表示其对应算法复杂度的渐进阶,从而比较算法的优劣.因此研究递归方程的解法意义重大.下文将分析并给出常用递归方程的3种解法.

1递归方程的解法

递归方程是对实际问题求解的一种数学抽象,递归的本质在于将原始问题逐步划分成具有相同解题规律的子问题来解决,原始问题与子问题仅在规模上有大小区别,并且子问题的规模比原始问题的规模要小.对于规模为n的原始问题,我们通常会寻找规模n的问题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推导出具有递归特性的运算模型.

根据递归方程的一般形式,常用的解法有三种,分别是递推法、公式法及生成函数法.下面就分别来分析其求解过程.

1.1递推法

当递归方程形式简单且阶数较低时,一般可以采用递推法求解,根据一步一步递推找到方程的递推规律,得到方程的解.下面举例说明： T(1)等于0

T(n)等于2T(n/2)+n2(n≥2)

T(n)等于2T(n/2)+n2等于2(2T(n/22)+(n/2)2)+n2

等于22T(n/2)2+2n2/22+n2

等于22(2T(n/23)+(n/22)2)+2n2/22+n2

等于23(2T(n/23)+22n2/(22)2)+2n2/(22)1+n2等

等于2kT(n/2k)+∑k-1i等于02in2(22)i递推到这里我们就可以发现递归规律,找到递归出口, T(1)等于0,令n等于2k 则可以得到如下结果：T(n) 等于2kT(1) +∑k-1i等于0n2(1/2)i)等于

n2(1-(1/2)k1-1/2)等于2n2-2n 上面得到方程的解,我们来分析其对应算法复杂性的渐进阶,根据渐进阶定理有：设有函数f(n),g(n）均是规模n的函数,则O(f(n))+O(g(n))等于O(max(f(n), g(n))).故有T(n)等于O(n2).

1.2公式法

对所需求解的递归方程进行观察,如果它是符合以下形式的常系数齐次线性方程,可用公式法求解.F(0)等于b0,

F(1)等于b1,等

F(k-1)等于bk-1,

F(n)等于a1F(n-1)+a2F(n-2)+等+akF(n-k) 在此,常系数是指a1 、a2、等ak是常数,线性指所有的F均为一次幂,齐次指无常数项.

解这类方程,可由F(n)项得出：F (n)-a1F(n-1)-a2F(n-2)-等

-akF(n-k) 等于0,寻找形如F(n)等于 xn的解.

令xn-a1xn-1-a2xn-2-等-akxn-k等于0；xn-k(xk-a1xk-1-等-ak) 等于0；即xk-a1xk-1-等-ak 等于0；

由此,我们得到了这类递归方程的特征方程,它有n个特征根,设为x1,x2,等,xk；其线性组合是F(n)的通解.即c1x1n+c2x2n+等+ckxkn等于F(n)；其中c1,c2,等,ck可由k个初始条件得到的线性方程组解出.

例如,常系数齐次线性方程组F(0)等于0,

F(1)等于1,

F(n)等于4F(n-2),(n＞1) 令F(n)等于xn；则xn 等于4xn-2；

xn - 4xn-2等于0 ；

x2-4等于0； （特征方程）

x1等于2；x2等于-2；（特征根）

设有c1,c2使F (n) 等于c1x1n+c2x2n；

由初始条件 F(0) 等于c1x10+c2x20等于c1+c2等于0,F(1)等于c1x11+c2x21等于2c1-2c2等于1；即c1+c2等于0,

2c1-2c2等于1解得c1等于1/4；c2等于-1/4；

∴F(n)等于2n/4-(-2)n/4即为以上递归方程的解.

1.3生成函数法

第三种方法是利用生成函数的方法,即已知一个数列a0,a1,a2,等,an,定义它的生成函数为一个形式幂级数：F(x)等于a0+a1x1+a2x2+等+anxn+等

我们寻找an的代数式.有了生成函数F(x),无需知道a0,a1,a2,等,an 的各项就可以设法找出它的生成函数的解析式,再将其展开成一个幂级数,则xn项的系数即为要求得的an.

以汉诺(Hanoi)塔问题的递归方程为例：T(1)等于1,

T(n)等于2T(n-1)+1,(n≥2) 该序列的生成函数为：T(x)等于T(1)x+T(2)x2+T(3)x3+等+T(n)xn+等(1)下面求T(n)的解析式.

由递归方程可得：T(2)-2T(1) 等于1,

T(3)-2T(2)等于1,

T(4)-2T(3)等于1,

等

T(n+1)-2T(n)等于1将(1)式×2x得：2xT(x)等于2T(1)x2+2T(2)x3+

2T(3)x4+等+2T(n)xn+1+等(2)(1)式-(2)式得,T(x) -2xT(x)等于 T(1)x+x2+x3+等+xn+等(1-2x)T(x)等于 x+x2+x3+等+xn+等

T(x)等于 等于 x1-x1-2x等于x(1-x)(1-2x)设T(x)等于A1-x+B1-2x等于A(1-2x)+B(1-x)(1-x)(1-2x)等于(A+B)-(2A+B)x(1-x)(1-2x)

应有x等于(A+B) - (2A+B)x

则A+B等于0,

2A+B等于-1解得A等于-1；B等于1

即T(x)等于-11-x+11-2x

用幂级数展开,得：T(x) 等于 (1+2x+22x2+23x3+...

+2nxn+...) - (1+x+x2+等+xn+等)

等于 (2-1) x+ (22-1) x2+ (23-1) x3+

等+ (2n-1) xn+等∴解出an等于2n-1；

在设定生成函数后,在求解解析式的过程中,需要消去中间的多余项,这就需要观察递归方程,上例中是采取了乘以一个系数相减的方法,在遇到具体问题时,可采取不同的方法, 比如移位、乘法、甚至求导,以求出要找的解析式.

2结束语

在算法设计中,很多问题可以采用递归解决.递归的引入往往使某些函数的定义和算法的描述更加清晰、明了.而且,递归对于一些用非递归无法完全描述的复杂函数和过程也能清楚地进行表达.根据递归方程的解的形式可以评价一个算法的时间复杂度,从而可以直接判断算法的优劣,因此递归方程求解在算法设计中至关重要.本文给出了3种求解递归方程的方法,采用这些方法就可解决一般的递归方程,对于递归方程的学习有十分重要的指导意义.参考文献：

[1]胡章平,王瑞胡.算法时间复杂度分析中递归方程求解方法综述[J].中国科技信息,2006(3).

[2]高见元.递归方程的分析[J].中国高新技术企业 2007(13).

[3]武继刚.关于递归方程T（n）等于a[1].T（n／c）＋d（n）的一般解[J].兰州大学学报(自然科学版),1989（4）.

[4]孙红丽,叶斌.浅析递归方程解法及其渐进阶表示[J].四川文理学院学报(自然科学版),2007（2）.

[5]王晓东.计算计算法设计与分析[M].北京：清华大学出版社,2008.

（责任编辑：杜能钢）