目录
前言
在讲到二叉树之前，一定要先把递归给讲了，只有先把基础学好了，才可以让学习的这棵二叉树更完整，更稳固一些。所以接下来，我会用代码和文字把递归的思想传递给大家，希望大家可以学到自己感兴趣的东西。
什么是递归
递归是一种思想，再变成上体现为方法的自调用。
举个例子说明：
实现某个数字的阶乘 1! = 1 2! = 1 * 2 3! = 1 * 2 * 3 4! = 1 * 2 * 3 * 4 5! = 1 * 2 * 3 * 4 * 5 6! = 1 * 2 * 3 * 4 * 5 * 6
我们最终要做的就是写一个方法，返回一个值：
public static int fun(int n) { return ...... }
我们需要考虑下方法块中要怎么写，观察阶乘，我们发现：
1! = 1 2! = 1! * 2 3! = 2! * 3 4! = 3! * 4 5! = 4! * 5 6! = 5! * 6
我好像发现了什么，如果我要获得n的阶乘，那是不是可以用n-1的阶乘乘以n？n-1的阶乘呢？是n-2的阶乘乘以n-1，依此类推。
方法块内，我们可以这样写：
public static int fun(int n) { return fun(n - 1) * n; }
fun(n - 1)就是n-1的阶乘，这就形成了递归，然后一直递归下去。但是有个问题，这里没有考虑n=1的情况，最终会出现负数，就没有了出口，这也是递归最重要的一点，一定要有出口，否则就是死循环。所以应该这么写：
public static int fun(int n) { if (n == 1) return 1; return fun(n - 1) * n; }
这样，一个求阶乘的方法就写好了，你以为很难？其实就这么简单，用事实验证了：越是难的东西越是需要简单来做，简单到你不相信这就是答案。
递归不得不知的经典案例：斐波那契数列
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89......
这个数列从第3项开始，每一项都等于前两项之和。
假如我要求第50位的数字，该怎么求？有上面的案例，不知道大家能不能自己写出来呢？
写不出来没关系，我将带领大家一起来解题，请大家跟上我的思路，我们开始。
我们先写一个方法体出来：
public static int fun(int n) { return ...... }
方便起见，我们就用上面的方法体，因为我要得到多少位的数字我只需要输入这个数，方法就会把这一位的数字返回给我。
上面文字已经说明：这个数列从第3项开始，每一项都等于前两项之和
那么规律就已经出现了，我们可以假设：
fun(50) = fun(49) + fun(48)
fun(49) = fun(48) + fun(47)
fun(48) = fun(47) + fun(46)
......
这里递归已经开始了，我们可以尝试着写一下这个方法块中的内容了：
public static int fun(int n) { return fun(n - 1) + fun(n - 2); }
你可能已经发现了问题，和前面一样的问题：没有考虑n=1的情况，所以就没有了出口。没错，但这里还要考虑n=2的情况 ，因为是从第三位开始数列才成立。
所以需要像上面那样，通过判断1，2给方法留出口：
public static int fun(int n) { if (n == 1 || n == 2) return 1; return fun(n - 1) + fun(n - 2); }
递归注意点
其实我们上面已经说到了一些注意点了，不知道大家能不能说下来？
没记住的也没关系，跟着博主一起看：
递归必须有出口，否则会导致栈内存溢出SOF（StackOverflowError）；
递归是有深度的，若是深度太深，也会导致栈内存溢出SOF；
关于栈：当调用一个方法时，会在栈上为这个方法分配属于这个栈帧的内存，哪个方法的栈帧则用来保存属于哪个栈帧的局部变量。
局部变量包括：方法参数，方法内声明的一些基本变量。方法结束时，栈帧上的内存才会清除。但是栈的内存并不是无限分配的，所以当出现递归深度太深的时候会导致栈内存溢出。
SOF和OOM
SOF: statckOverFlowError 栈内存溢出
OOM: OutOfMemoryError 堆内存溢出
内存溢出指的是剩余内存不足以分配给请求的资源，此时就出现了内存溢出。可能的原因是：
创建大对象
内存泄漏的不断累积。内存泄漏累积到一定程度，会出现堆内存溢出
内存泄漏指的是分配出去的内存因为一些原因无法回收，此现象就叫内存泄漏。
内存泄漏和内存溢出的关系：
内存泄漏累积到一定程序才会造成内存溢出，并不是内存泄漏一旦出现，则立即出现内存溢出
出现内存溢出并不一定是由于内存泄漏造成的，还可能是因为创建了大对象。
结语
到这里，递归就讲完了，有不明白的小伙伴可以留言一起讨论，下一篇，我们二叉树见。
