递归不想前面简单的算法一样，可以直接得到时间运行时间，因为递归项依赖前一项。
递归方程求解的是一般式，递归方程需要满足非一般式，所以有界限这一说。
递归方程求解方法：替换方法、递归树方法、主方法。
替换方法
用替换方法解某个递归方程时，分两步。首先猜测问题解的某个界限，然后用数学归纳法证明所猜测解的正确性。
例：替换方法解
解：猜测解为（这个主要靠经验），假设这个界限对于
成立，即存在某个常数
，
成立。现在要证明
。将假设代入递归方程得：
最后一步在时成立。
假设是递归方程的唯一边界条件，那么对于
，
与
发生矛盾。因此，归纳法中的归纳基础不成立。
假设为唯一边界条件，那么
，
时成立，在渐进表示法里，，那么
，
时，
得证。