递归和分治

递归算法

直接或者间接调用自己的算法是递归算法。

递归算法的特点是：

• 结构清晰，可读性强，容易使用数学归纳法证明正确性
• 运行效率低

我们有几种方法来优化递归算法：

• 采用用户定义的栈来模拟系统的递归调用
• 用递推来实现递归函数
• 使用Cooper变换、反演变换将递归转换为尾递归，进而用迭代求解

分治算法

将一个难以解决的问题分成一些规模较小的问题，以便分而治之，各个击破。