《数据结构与算法-王争》学习笔记，记录备查

可用递归解决的问题的三个条件

• 一个问题的解可以分解为几个子问题的解

• 这个问题和子问题之后的子问题，除了数据规模不同，求解思路完全一致。

• 存在递归终止条件

如何编写递归代码

关键：写出递归公式，找到终止条件

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

递归使用时需要注意的问题

堆栈溢出

我们知道函数的临时变量时使用栈来保存的，当函数递归的深度大于栈的大小时，就发生溢出。

规定递归的深度可以部分解决堆栈的溢出的问题。因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算，不合适使用该方法。

递归警惕重复计算

递归使用时，还会出现重复计算的问题。

可通过一个数据结构（如散列表）暂存以计算的值，等递归时先查询是否已经计算过，如以计算直接返回即可。

递归还有些其他问题，如空间复杂度高、过多的函数调用会耗时较多等。

递归改写成非递归

递归代码归根结底是利用了栈的出栈、入栈，如果我们自己模拟栈的操作，理论上来说任何递归都可以改写成非递归方式。