如何理解“递归”

递归是一种应用非常广泛的算法（或者编程技巧）。

递归的三个条件

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

如何编写递归代码

写递归代码最关键的是<font color=red>找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再失调终止条件，最后将递推公式和终止条件，最后将递推公式和终止条件翻译成代码。</font>

递归代码的注意事项

1.递归代码要警惕堆栈溢出

函数调用的机制是通过堆栈来实现的，递归代码层次过深会容易溢出堆栈空间。

2.递归代码要警惕重复计算

递推公式分解时，会存在大量重复计算。

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

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

在开发过程中，要根据实际情况来选择是否需要用递归的方式来实现。

是否所有的递归代码都可以改为迭代循环的非递归写法？

笼统地讲，是的。因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知而已。

课后思考

我们平时调试代码喜欢使用IDE的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？

递归使用不多，没有遇到过类似的问题，但感觉可以使用单元测试来调度，不管是通过进行查看结果，也能Mock数据来验证递归公式是否正确。