递归

写递归代码的关键点

①写出递推公式，找到终止条件

②我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢？

如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。因为后面的解题思路都跟这一层一样，经典案例就是汉诺塔。

总的来说，只要遇到递归，分析出递归第一层的关系，之后我们就把它抽象成一个递推公式（因为后面每一层递归的思路一样），不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

③警惕栈溢出，我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错。

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

④警惕重复运算

什么情况下用递归？

同时满足下面三个条件，即可使用递归

①一个问题可以分解为几个子问题的解（子问题就是数据规模更小的解）

②分解后的子问题，除了数据规模不同，解题思路与父问题完全相同

③有递归终止条件，否则会“死龟”

还要注意，递归有利有弊，利是递归代码的表达力很强，写起来非常简洁，而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。

递归怎么调试？

1.打印日志发现递归值。

2.结合条件断点进行调试。