数据结构与算法 - 算法 - 递归
约 475 字大约 2 分钟
数据结构与算法递归
2023-09-08
《数据结构与算法-王争》学习笔记，记录备查
可用递归解决的问题的三个条件
一个问题的解可以分解为几个子问题的解
这个问题和子问题之后的子问题，除了数据规模不同，求解思路完全一致。
存在递归终止条件
如何编写递归代码
关键：写出递归公式，找到终止条件
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
递归使用时需要注意的问题
堆栈溢出
我们知道函数的临时变量时使用栈来保存的，当函数递归的深度大于栈的大小时，就发生溢出。
规定递归的深度可以部分解决堆栈的溢出的问题。因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算，不合适使用该方法。
递归警惕重复计算
递归使用时，还会出现重复计算的问题。
可通过一个数据结构（如散列表）暂存以计算的值，等递归时先查询是否已经计算过，如以计算直接返回即可。
递归还有些其他问题，如空间复杂度高、过多的函数调用会耗时较多等。
递归改写成非递归
递归代码归根结底是利用了栈的出栈、入栈，如果我们自己模拟栈的操作，理论上来说任何递归都可以改写成非递归方式。