递归

    每个递归函数都有两部分：基线条件（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;

    }

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

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

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