递归 #
比如在影院，你不知道你现在坐在第几排，就可以问前一排的人他在第几排，如果前面的人也不知道，再问前一排人，直到问道第一排。再把这个数字 一排一排传回来，就知道在第几排了。这个过程就是递归。去的过程是“递”，回来的过程是“归”。
递归需要的三个条件 #
- 一个问题的解可以分解为几个子问题的解何为子问题？子问题就是数据规模更小的问题。 比如你要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。 比如你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。
- 存在递归终止条件。 例子中第一排的人不需要再继续询问任何人，就知道自己在哪一排，这就是递归的终止条件。
递归代码最关键的是写出递推公式，找到终止条件。
堆栈溢出 #
函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟 机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
比如前面电影院的例子，如果我们将系统栈或者 JVM 堆栈大小设置为 1KB，在求解 f(19999) 时便会出现如下堆栈报错：
Exception in thread "main" java.lang.StackOverflowError
如何避免出现堆栈溢出 #
可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了， 直接返回报错。
重复计算 #
使用递归时还会出现重复计算的问题。可以通过一个数据结构（比如散列表）来保存已经求解过的递归函数。