什么是递归
递归式一个过程或函数直接或间接调用自身的一种方法，它可以把一个大型的问题层层转化为一个与原问题相似、但规模较小的问题来求解。
递归的思想其实不是编程特有的，我们早在九年义务教育中就接触过了。如斐波那契数列：
1，1，2，3，5，8，13，21，34，……
F(n) = F(n-1) + F(n-2)，n ≥ 2
使用递归的条件
递归的优点：在一些特定的场景使用递归能让我们的代码简单明了，不用递归就很难解决
递归的缺点：不能滥用，因为有时候循环的效率更高，而且递归一个不注意可能就会导致栈溢出
那我们什么时候使用递归呢？一般来说要满足以下三个条件：
- 待解决的问题可以被转化成多个子问题来解决，而且这些子问题的求解方法与原问题完全相同，只是数量规模上有所不同
- 递归调用的次数必需是有限的
- 必需有结束递归的条件或者边界
递归调用的内部过程
递归调用图
如上图，可以看出 main 方法之后就进入了递归，一直传递到 F(4)，F(4) 得到计算结果后给回 F(3), F(3) 再根据 F(4) 的结果计算得到自己的结果再给到 F(2)。如此类推，层层往上直到 main 方法。
总结下，递归过程一共就两个阶段：
- 传递，一直不断缩小问题规模，直到最终停止条件或者边界
- 回溯，沿着传递的路线带着结果返回，直至入口处
在上面两个阶段中，系统会完成一系列操作，如下
传递前：
- 为被调用过程的局部变量分配存储区
- 将所有的实参、返回地址等信息传递给被调用过程保存
- 将控制转移到被调过程的入口
回溯前：
- 保存被调过程的计算结果
- 释放被调过程的数据区
- 依照被调过程保存的返回地址将控制转移到调用过程
