【摘要】：有些递归方程可以看成一个差分方程，因而可以用解差分方程的方法来解递归方程。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。
2.1.4 递归方程求解的方法
算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。
递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法：
①代入法
这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。
②迭代法
这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。
③套用公式法
这个方法针对形如：T (n)=aT (n / b)+f (n)的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。
④差分方程法
有些递归方程可以看成一个差分方程，因而可以用解差分方程（初值问题）的方法来解递归方程。然后对得到的解作渐近阶的估计。
⑤母函数法
这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
