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

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

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

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

  • 存在递归终止条件

如何编写递归代码

关键:写出递归公式,找到终止条件

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

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

堆栈溢出

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

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

递归警惕重复计算

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

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

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

递归改写成非递归

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