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

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

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

        3.存在递归终止条件。

    2如何编写递归代码？

        写递归代码最关键的是写出递归公式，找到终止条件，然后再将递推公式转化为代码。

        用一个例子来理解~

        假设有n个台阶，每次可以跨1个台阶或者2个台阶，那么这n个台阶有多少种走法？

        实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶， 第二类是第一步走了2个台阶。所以，n个台阶的走法=先走1阶后剩下n-1个台阶的走法+先走2阶后剩下n-2个台阶的走法，公式如下：

        f(n)=f(n-1)+f(n-2)   

        终止条件为：f(1)=1,f(2)=2.

        转化成代码：

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

        递归分为两个过程，去的过程叫“递”，回来的过程叫“归”。

        计算机擅长做重复的事情，所以递归正和它的胃口。

    3递归代码要警惕堆栈溢出

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

        如何避免出现堆栈溢出呢？

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

        一个伪代码的例子：

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

    4递归代码要警惕重复计算

        使用递归的时候还会出现重复计算的问题，比如我们刚才讲的例子：

        可以看到，同一个f(k)我们会计算好几次。为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的f(k)。每次递归调用到f(k)的时候，先看下是否已经求解过了，如果是，则直接从散列表中取值返回。

        OK，优化后的代码如下：

    5怎么将递归代码改写为非递归代码？

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

        那如何将递归代码改写为非递归代码呢？

        例一：

        递归代码：

        非递归代码：

        例二（上台阶的例子）：

        递归代码：

        非递归代码：

        所有的递归代码都可以改为这种迭代循环的非递归写法吗？

        是的。

        因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。

        但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决前面讲到的某些问题，徒增了实现的复杂度。

    内容小结

        递归是一种非常高效、简洁的编码技巧，只要满足“三个条件”的问题就可以通过递归代码来解决。不过递归代码也比较难写、难理解。编写递归代码的正确姿势是写出递推公式，找出终止条件，然后翻译成递归代码。递归代码虽然简洁高效，但是也有很多弊端，比如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以在编写递归代码的时候，一定要控制好这些副作用。