递归(Recursion)
Varsion

递归是一种应用非常广泛的算法(或者编程技巧)。很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等等。

递归的满足条件:

  • 一个问题的解可以分解为几个子问题的解
  • 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
  • 存在递归终止条件

如何写出递归代码:

写递归代码最关键的是写出递推公式,找到终止条件,剩下将递推公式转化为代码就很简单了。

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

编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤

警惕堆栈溢出

函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。

对于堆栈溢出,可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度(比如 1000)之后,就不继续往下再递归了,直接返回报错。

但这种做法并不能完全解决问题,因为最大允许的递归深度跟当前线程剩余的栈空间大小有关,事先无法计算。如果实时计算,代码过于复杂,就会影响代码的可读性。所以,如果最大深度比较小,比如 10、50,就可以用这种方法,否则这种方法并不是很实用。递归代码要警惕重复计算。

警惕重复计算

为了避免重复计算,我们可以通过一个数据结构(比如散列表)来保存已经求解过的 f(k)。当递归调用到 f(k) 时,先看下是否已经求解过了。如果是,则直接从散列表中取值返回,不需要重复计算。

在时间效率上,递归代码里多了很多函数调用,当这些函数调用的数量较大时,就会积聚成一个可观的时间成本。

在空间复杂度上,因为递归调用一次就会在内存栈中保存一次现场数据,所以在分析递归代码空间复杂度时,需要额外考虑这部分的开销。

将递归代码改写为非递归代码

递归有利有弊,利是递归代码的表达力很强,写起来非常简洁;而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。

递归本身就是借助栈来实现的,只不过使用的栈是系统或者虚拟机本身提供的。

如果写代码时在内存堆上实现栈,手动模拟入栈、出栈过程,这样任何递归代码都可以改写成看上去不是递归代码的样子。


  • Post title:递归(Recursion)
  • Post author:Varsion
  • Create time:2020-08-05 21:01:37
  • Post link:https://blog.varsion.cn/post/47f718a8.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments