[What]数据结构与算法 -> 递归

课程:王争 –> <数据结构与算法之美>

之前对递归的理解比较浅显,现在再来梳理一下。

递归的3个条件

当一个例子满足以下3个条件时,它就可以被使用递归来解决:

  1. 一个大问题可以被分解为多个子问题的解
  2. 大问题和被分解的子问题求解思路一样
  3. 存在递归终止条件(基线条件)

编写递归的流程

  1. 根据当前问题,得出递推公式
  2. 得出终止条件
    • 有的时候终止条件可能有多个,需要仔细推导
  3. 将递推公式和终止条件翻译为代码

要解决一个大问题,就要尽量的将其分解为尽量多的小问题。

在思考小问题的时候,有点是需要特别注意的:

在解决一个小问题时,要假设其他的问题都已经被解决了。

目前只需要集中精力思考:
1. 该问题的解决方案
2. 该问题与其他问题的接口

递归需要注意的问题

栈溢出

有两种情况会导致栈溢出:

  1. 终止条件设置得不够完善,导致无限压栈
  2. 函数调用的层级太多了
    • 可以通过限制调动层级或者以循环的方式代替递归写法来解决此问题

也正是因为每次调用都会有压栈的操作,导致递归的时间复杂度不低!

  • 比如简单的单向递归的时间复杂度不是O(1)而是O(n)

重复计算

当递归中有分支时,很可能会出现这种情况: 在一个分支中已经运行了一次解,而在另外一个分支中也将会运行一次该解。

那么这就会导致CPU时间的浪费。

解决方案是:使用一个数据结构将已经运行的解的结果存储下来,当有其他分支运行该解时便直接从数据结构中取出结果返回即可。

Last Updated 2018-11-07 Wed 22:35.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)