数据结构-0-递归

递归简介

递归需要满足的三个条件：

  • 一个问题可以被拆解成几个子问题
  • 子问题与原问题的解题思路是相同的，只有数据规模不一样
  • 需要有终止条件，当数据规模足够小，能够直接得出结果并返回

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

递归注意事项

  • 递归代码写的不合理的时候会出现 堆栈溢出 的问题：

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

    ​ 限制递归调用的最大深度（超过指定调用深度就进行报错，需要使用局部变量，需要注意解决线程安全问题）；另外最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。

  • 递归的方法层层嵌套，可能出现对于同样的调用做了多次计算。解决办法：

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

  • 递归要注意是否会出现环的问题，一旦出现 A-B-C-A这种环的存在，就会发生死循环。解决办法：

    1. 有人说可以使用散列表存储一个调用结果，如果存在重复调用就是存在环了。比如调用A的到C（保存到散列表，下同） ,调用C得到B ,抵用B得到A,此时的A已经得到过了，说明存在环。===数据规模大的时候占用空间也很大

    2. 有人说可以步长法判断 : 从起点开始分别以 2x,1x 速度出发两个指针 , 当遇到 null 停止 , 相遇点为 null 时说明没有环 。暂时还没太理解【后续继续补充】

  • 递归的调试是一个问题，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。解决办法：

    1. 打印日志发现，递归值。
    2. 结合条件断点进行调试。