10|递归

如何理解递归

递归是一个广泛的编程技巧，如DFS深度优先搜索、前中后序二叉树遍历。

递归满足的三个条件

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

2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。

3.存在递归终止条件。

如何编写递归代码

关键：

1.如何将大问题分解为小问题的规律，基于此写出递推公示，在推敲终止条件，最后将地推公式和终止条件翻译成代码

2.递归代码不好理解，人脑没办法把这个“递”和“归”的过程想清楚，人脑更适合平铺直叙的四维方式，所以不要试图搞清楚计算机每一步是怎样执行的，会被绕进去。

3.一个问题A可以分解为若干子问题B、C、D,假设B、C、D已经解决，在此基础上思考如何解决问题A，只需思考问题A与问题B、C、D两层的关系即可，不需要一层一层往下思考子问题与子子问题的关系，屏蔽掉递归细节

警惕堆栈溢出

递归代码会造成堆栈溢出，堆栈溢出会造成系统崩溃。

函数调用使用栈来保存临时变量，每调用一个函数，都会讲临时变量封装成栈帧压入内存栈，等函数执行完成再出栈，一般情况系统栈和虚拟机栈空间都不大，当递归代码求解数据规模很大时，调用层次很深，一直压入栈就会有堆栈溢出的风险。

如何避免

限制递归最大深度(适合于最大深度比较小的情况)

警惕重复计算

利用散列表来保存已经求解过的值

问题：

时间效率上，递归游很多函数调用，函数调用交大时，就回积聚成可观的时间成本

空间复杂度上，递归调用一次就回在内存栈保存一次现场数据，所以分析空间复杂度的时候需要额外考虑这部分的开销

递归改为非递归

（1）递归表达力强，简洁

（2）空间复杂度高，有堆栈溢出的风险，存在重复计算，过多函数调用耗时较多

所以可以根据实际情况选择是否用递归来实现，可以将递归改为非递归实现

---

写在最后

问题：

1.对于无线递归的问题

（1）限制递归深度

（2）检测递归环

2. 递归代码如何调试

打印日志发现递归值，结合断点进行调试。