递归式：

一个等式或者不等式，通过更小的输入上的函数来描述一个函数。
算法中，用子问题解决大问题

解递归式的三种方法：

代换法、递归树方法、主方法

代换法(Substitution method)
我们猜测一个界，然后用数学归纳法证明这个界是正确的

递归树方法(Recursion-tree method)
将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用便捷和技术来求解递归式

主方法(Master method)
可以求解类似T(n) = aT(n/b) + f(n)的解
解决的分治算法是，生成了a个子问题，每个子问题的规模是原问题规模的1/b，分解和合并步骤总共花费时间为f(n)