递归方程求解方法综述（精品论文）.doc

递归方程求解方法综述摘要：随着计算机科学的逐步发展，各种各样的算法相继出现， 我们需要对算法进行分析，以选择性能更好的解决方案算法分析 中计算复杂度常用递归方程来表达，因此递归方程的求解有助于分 析算法设计的好坏阐述了常用的3种求解递归方程的方法：递推 法、特征方程法和生成函数法这3种方法基本上可以解决一般规 模递归方程的求解问题关键词：递归；递推法；特征方程；生成函数0引言寻求好的解决方案是算法分析的主耍目的，问题的解决方案可能 不只一个，好的方案应该执行时间最短，同时占有存储空间最小， 故算法分析一般考虑时间复杂性、空间复杂性两方面的参数在算 法分析时我们采用时间耗费函数来表示时间参数，用当问题规模充 分大时的时间耗费函数的极限表示时间复杂度一般算法对应的时间耗费函数常用递归方程表示，找出递归方程 的解，就可以表示其对应算法复杂度的渐进阶，从而比较算法的优 劣因此研究递归方程的解法意义重大下文将分析并给出常用递 归方程的3种解法1递归方程的解法递归方程是对实际问题求解的一种数学抽象，递归的本质在于将 原始问题逐步划分成具有相同解题规律的子问题来解决，原始问题 与子问题仅在规模上有大小区别，并且子问题的规模比原始问题的 规模要小。

对于规模为n的原始问题,我们通常会寻找规模n的问 题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推 导出具有递归特性的运算模型根据递归方程的一般形式，常用的解法有三种，分别是递推法、公式法及生成函数法下面就分别来分析其求解过程1.1递推法当递归方程形式简单且阶数较低时，一般可以采用递推法求解， 根据一步一步递推找到方程的递推规律，得到方程的解下面举例 说明：t (1)=0t(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)l+n2…=2kt (n/2k) + Sk-1 i=02in2 (22) i递推到这里我们就可以发现递归 规律，找到递归出口，t⑴二0,令n二2k则可以得到如下结果：t(n) =2kt(l) +Sk-li=0n2(l/2)i) =n2(l-(l/2)kl-l/2)=2n2-2n上面得到方程的解，我们来分析其 对应算法复杂性的渐进阶，根据渐进阶定理有：设有函数f(n) ,g(n) 均是规模 n 的函数，则 o (f (n)) +o (g (n)) =o (max (f (n), g (n))) □故 有 t (n) =o (n2) o1・2公式法对所需求解的递归方程进行观察,如果它是符合以下形式的常系数齐次线性方程，可用公式法求解。

f(O)=bO：f(l)=bl;……f(k-l)=bk-l;f (n) =alf (n-1) +a2f (n-2) +•••+akf (n-k)在此，常系数是指 al、 a2、……ak是常数，线性指所有的f均为一次幕，齐次指无常数项解这类方程，可由f(n)项得出:f (n)-alf(n-1)-a2f(n-2)—-akf (n-k)二0;寻找形如 f(n)= xn 的解令 xn-alxn-l~a2x门-2 akxn-k=0； xn-k(xk-alxk-1 ak) =0；艮卩 xk-alxk-1 ak =0；由此，我们得到了这类递归方程的特征方程，它有n个特征根， 设为xl, x2, •••, xk；其线性组合是f (n)的通解即clxln+c2x2n+… +ckxkn=f (n)；其中cl, c2,…，ck可由k个初始条件得到的线性方 程组解出例如，常系数齐次线性方程组f (0)=0;f ⑴二 1；f (n)=4f (n-2) : (n>l)令 f (n)=xn；则 xn =4xn~2；xn - 4xn-2=0 ；x2-4二0；(特征方程)xl=2； x2=-2；(特征根)设有 cl, c2 使 f (n) =clxln+c2x2n；由初始条件f(o)二clxl0+c2x20二cl+c2二0;f(1)二clxll+c2x21二2cl-2c2二1；即 cl+c2二0;2cl-2c2=l 解得 cl=l/4； c2=-l/4；・・・f (n) =2n/4-(-2) n/4即为以上递归方程的解。

1・3生成函数法第三种方法是利用生成函数的方法，即已知一个数列a0, al, a2, •••, an,定义它的生成函数为一个形式幕级数：f (x)=a0+alxl+a2x 2+• • •+anxn+• • •我们寻找an的代数式有了生成函数f(x),无需知道a0, al, a2, an的各项就可以设法找出它的生成函数的解析式，再将其展开成一个幕级数，则xn项的系数即为耍求得的ano以汉诺(hanoi)塔问题的递归方程为例：t(l)=l;t(n)=2t(n-l)+l; (n^2)该序列的生成函数为：t (x) =t (l)x+t (2) x2+t (3)x3+・・・+t (n) xn+…(1)卜面求 t (n)的解析 式由递归方程可得:t(2)-2t(1) =1:t(3)-2t(2)=l;t(4)-2t(3)=l;t (n+l)-2t (n)=l 将(1)式 X2x 得:2xt (x)二2t (l)x2+2t (2)x3+2t (3) x4+…+2t (n) xn+l+…(2) (1)式-(2)式得，t (x) _2xt (x)=t (1) x+x2+x3+・・・+xn+…(1 -2x) t (x)二 x+x2+x3+・・・+xn+…t(x)= = xl-xl~2x=x(1-x) (l~2x)设t (x)二al-x+bl-2x二a(l-2x)+b(l-x) (l~x) (1 -2x)二(a+b)-(2a+b)x(l-x) (1 一2x)应有 x二(a+b) -(2a+b)x则 a+b二0;2a+b=-l 解得 a=-l ； b=l即 t (x)二-11-x+11-2x用幕级数展开，得：t(x) = (1+2x+22x2+23x3+・・・+2nxn+・・・) 一 (l+x+x2+・・・+xn+•…)=(2-1) x+ (22-1) x2+ (23-1) x3+…+ (2n~l) xn+・・・.・.解出an=2n~l:在设定生成函数后，在求解解析式的过穆中，需要消去中间的多 余项，这就需要观察递归方程，上例中是采取了乘以一个系数相减 的方法，在遇到具体问题时，可采取不同的方法，比如移位、乘 法、甚至求导，以求出要找的解析式。

2结束语在算法设计中，很多问题可以采用递归解决递归的引入往往使 某些函数的定义和算法的描述史加清晰、明了而且，递归对于一 些用非递归无法完全描述的复杂函数和过程也能清楚地进行表达 根据递归方程的解的形式可以评价一个算法的吋间复杂度，从而可 以直接判断算法的优劣，因此递归方程求解在算法设计中至关重 要本文给出了3种求解递归方程的方法，采用这些方法就可解决 一般的递归方程，对于递归方程的学习有十分重要的指导意义参 考文献：[1] 胡章平，王瑞胡•算法时间复杂度分析中递归方程求解方法综 述[j]・中国科技信息,2006(3)・[2] 高见元•递归方程的分析[j]•中国高新技术企业2007(13).[3] 武继刚•关于递归方程t (n) =a[l]. t (n / c) +d (n)的一般 解[j].兰州大学学报(自然科学版),1989 (4).[4] 孙红丽，叶斌•浅析递归方程解法及其渐进阶表示[j]・四川文 理学院学报(自然科学版),2007 (2)・[5] 王晓东•计算计算法设计与分析[m]・北京：清华大学出版社，2008.。