递归的Java实现

递归是一种应用非常广泛的算法（或者编程技巧）。递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。

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

问题：N级台阶（比如100级），每次可走1步或者2步，求总共有多少种走法？

分析：如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-2级台阶，有f(n-2)种跳法。这就表示f(n)=f(n-1)+f(n-2)，即斐波那契数列。假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级，f(2)=2。

编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归代码要警惕重复计算

为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。

递归代码要警惕堆栈溢出

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

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

递归本身就是借助栈来实现的，如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，便可以将递归改成非递归。