方法或者函数调用自身的方式称为递归调用，调用称为递，返回称为归。
用栈的数据结构加上简单的逻辑算法实现业务功能。
递归特点
- 一个问题的解可以分解为几个子问题的解
- 原问题与分解后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
关键：
找到如何将大问题分解为小问题的规律，基于此写出递推公式，推敲终止条件，最后将递推公式和终止条件翻译成代码。
遇到递归，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤，把它抽象成一个递推公式。
递归问题
- 栈溢出1
函数调用会使用栈来保存临时变量，每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时才出栈。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有栈溢出的风险。
解决：1.最大深度比较小的情况，在代码中限制递归调用的最大深度。2.数据规模较大的情况，用非递归-循环代码实现。 - 重复计算
解决：通过一个数据结构（散列表）来保存已经求解过的f(k)，当递归调用到f(k)时，先看下是否已经求解过。如果是则直接从散列表中取值返回，不需要重复计算。 - 时间空间成本
扩展
所有的递归代码都可以改为迭代循环的非递归写法
递归本身依然是借助栈实现的。抽象出递推公式、初始值、边界条件，用迭代循环实现。
递归代码的调试方法
日志中打印递归值
添加条件语句进行断点调试
检测递归中环的存在
通过散列表保存已计算完成的数据，每次递归调用，先去散列表中查询，没有查到的话就加入，如果存在则表示存在环。