要理解递归、首先 要理解递归
递归就像我们查字典的时候
当查找一个词时，发现它的解释中某个词仍然不懂，于是开始查这第二个词
像千钧一发这个词的解释中 千钧一词仍然不懂
于是开始查找千钧的意思
在千钧的解释中
一石为四钧 一石这个词还是不懂
于是继续查找 一石
到这里我们明白了 一石指的是120斤
就像这样我们一直查找，直到有一个词的解释完全明白为止
那么我们就可以开始后退
一石指120斤，那么4钧为1石，则1钧为30斤
则千钧为3万斤
到此我们就彻底明白了千钧一发的意思
递归 递归，先有递再有归
递的意思就是将问题拆解成子问题来解决
子问题再拆解为子问题，直到被拆解的问题无需再拆解为更细的子问题时
就像在字典中一直查找不明白的词语 的情况
归的意思是 最小的子问题得到解决了，那么它的上一层也会有由于它的解决而被解决，上一层的子问题解决了，那么上上层的问题自然也就解决了，一直到开始的问题被解决
在编程中
递归简单来说，就是如果在函数中存在着调用函数本身的情况，这种就可以称为递归
我们以一个阶乘函数的实现为例
可以看到在 factorial 函数中，存在着一个 factorial 函数的调用，所以这个函数就是递归函数
factorial 函数我们简写下，改为f
我们以阶层f 6 为例，看下它的递和归
求解问题f 6，n为6，n大于1
则return n * f n-1，当前n为6，则 f6 = 6 * f5
所以 f 6 被拆解为 f 5 的子问题
同理 f 5 = 5 * f 4 也需要进一步拆解
f 4 = 4 * f 3
f 3 = 3 * f 2
f 2 = 2 * f 1
当n等于1时f 1 = 1
到这时 f 1 的问题解决了，无法继续往下递了
进行归
既然f1解决了，那么 f 2 只依赖于f1 所以f2问题也可以解决了
f 3 依赖 f 2的结果，f2解决了那么f3也可以解决了
同理 f4、f5、f6都可以解决
所以递归的本质就是把问题拆分成具有相同解决思路的子问题
直到最后被拆解的子问题再也不能拆分
解决了最小粒度可求解的子问题后，在归的过程中自然而然地就解决了最开始的问题
我们在看个稍微进阶点的
青蛙跳台阶的问题
一只青蛙可以一次跳1级台阶或者一次跳2级台阶
跳上第1级台阶只有1种跳法 直接跳1级即可
跳上第2级台阶有两种跳法
每次跳1级，跳两次
或者1次就跳两级
问 要跳上第n级台阶有多少种跳法呢？
仔细看题目，一只青蛙一次只能跳1级或者2级台阶
自上而下的思考，也就是说如果要跳到n级台阶只能从 n-1 或 n-2级开始跳
所以问题就转化为跳上 n-1 和n-2级台阶的跳法了
如果f n 代表跳到n级台阶的跳法
那么从以上分析可得 f n的函数为 f(n) = f(n -1) + f(n -2)
显然这就是我们要找的问题和子问题的关系
而显然当 n = 1和n = 2时，即跳到1 2 阶台阶时是问题的最终解，也是已知解
n=1时有一种跳法，n=2时有两种跳法
那么跳到第6层时有多少种跳法
可以看作求解问题 f 6
n = 6时
返回 f 5 + f4 那么 f6被拆解为 f5 和 f4 的子问题
继续 递 下去，求解 f5 则需要知道 f4和f3
求解 f4 需要知道 f3 和 f2
求解 f 3 需要知道 f2 和 f1
f2已知等于2
f1已知等于1
问题已经得到最小化，无法继续递下去了
进行归操作
f3 = f 2 + f 1，f2有2种跳法f1有1种，所以 f3 = 2 + 1 = 3
f4=f3+f2，f3有3种，f2有2种
所以f4有5种跳法
f5=f4+f3，f4有5种，f3有3种
所以f5有8种跳法
f6=f5+f4，f5有8种，f4有5种
所以f6有13种
也就是说青蛙跳上第6阶有13种不同跳法
写递归代码的关键就是找到如何将大问题分解为小问题的规律
然后再推敲终止条件
