每个递归函数都有两部分：基线条件（base case） 和 递归条件（recursive case）。递归条件指的是 函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无线循环。
递归需要满足的三个条件
1.一个问题的解可以分解为几个 子问题 的解；
2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样；
3.存在递归终止条件。
如何编写递归代码？
写递归代码最关键的是写出递推公式（找到如何将大问题分解为小问题的规律），找到终止条件，剩下将递推公式转化为代码就很简单了。
要点：编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归代码要警惕堆栈溢出
在递归过程中，我们需要注意堆栈溢出的问题。在递归过程中，函数会被压入栈中，如果递归调用的深度过高，就会有用溢出栈的风险。
我们可以通过限制代码中递归调用的最大深度的方式解决这个问题。递归调用超过一定深度之后，就不在继续调用下去。
递归代码要警惕重复计算
就像斐波那契数列一样，如果不做一些缓存的处理，那么就会出现大量的重复计算，大大增加了时间复杂度。
将递归代码改成非递归代码
f(x) =f(x-1)+1；
f(int n) {
let ret = 1;
for (let i = 2; i <= n; ++i) {
ret = ret + 1;
}
return ret;
}
是不是所有的递归代码都可以改为这种迭代循环的非递归写法呢？
笼统地讲，是的。因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。
但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决前面讲到的某些问题，徒增了实现的复杂度。
网友评论