学习递归之前，我们可以首先思考一下“递推”这个概念？
因为，人的思想是更适合 【递推】 而不是 【递归】。
一、斐波那契数列
1️⃣递推
我们举一个小例子，给出下列的一组数据，那么第10个数字是多少？
1，1，2，3，5，8....
正常人的思维肯定是，从前边的数据总结规律，然后从前向后，也就是“自低向上”寻求解决问题的思路，这个过程就是 【递推】 的过程，代码如下：
// 我们传入的n是从1开始计算的，第五个 private static int fibonacci1(int n) { // 创建一个数组，用来存放结果 int[] result = new int[n]; result[0] = result[1] = 1; // 从第三项开始递推，知道第n-1 for(int i = 2 ; i <= n-1 ; i++){ result[i] = result[i-1] + result[i-2]; } return result[n-1]; }
时间复杂度： O(n)。
空间复杂度： O(n)。
2️⃣递归
递归的思路恰恰是相反的，递归的思路是要明确，我们要计算第九个，只要知道第7个和第8个就可以了，以此类推，想要知道第7个就只需要知道第6个和第5个就可以了，一直进行推算直到需要知道第一个和第二个为止。
其实我们可以给这个递推过程推导出一个方程如下，我们可以把他解释为”状态转移方程“：
f(n)={ 1,n=1,2 f(n−1)+f(n−2),n>2
我们甚至可以画出如下的图形：
我们可以专门定义一个函数fibonacci2(int n)，这个函数就是用来求第n个斐波那契数列的值的函数，代码如下：
private static int fibonacci2(int n) { if (n == 1 || n == 2) return 1; return fibonacci1(n - 1) + fibonacci1(n - 2); }
f(n) = f(n-1) + f(n-2) = f(n-2) + f(n-3) + f(n-3) + f(n-4)，每一项都裂变出两项，最终得出结论：O(2^n)
3️⃣重复子问题
我们再一次看看上边的图，会发现一个问题，很多的计算都是重复的，不多说，仅仅是上图中的内容，f(7)出现了3次，f(8)出现了两次，大量的计算是很消耗资源的，那有没有什么办法防止这些重复的计算呢？
我们可以使用一个备忘录，进行存储，每次计算完成之后将结果保存在一个数组（集合）中，代码如下：
// 使用一个数组memo进行保存，memo的下标代表第几个，值就是结果 private static int fibonacci2(int[] memo,int n) { // 如果存在就直接返回 if (memo[n] > 0){ return memo[n]; } if (n == 0 || n == 1){ memo[n] = 1; } else { memo[n] = fibonacci2(memo,n-1) + fibonacci2(memo,n-2); } return memo[n]; }
时间复杂度为 O(n)，每一次计算的结果都进行保存，相当于计算n个结果。
4️⃣性能
我们比较一下三种方法的性能：
public static void main(String[] args) { long start = System.currentTimeMillis(); System.out.println(fibonacci1(40)); long end = System.currentTimeMillis(); System.out.println(end - start); start = System.currentTimeMillis(); System.out.println(fibonacci2(new int[40],40)); end = System.currentTimeMillis(); System.out.println(end - start); start = System.currentTimeMillis(); System.out.println(fibonacci3(40)); end = System.currentTimeMillis(); System.out.println(end - start); }
我们会发现，当有了【备忘录】之后，性能得到了大幅度的提升，这就是所谓的【空间换时间】。
二、抢5游戏
两个人先从【数字1或2】中选择一个，然后，另一个人在这个基础上选择加1或者加2，正好加到5为止，如果是你怎么能保证这个游戏必赢呢？
这个问题很简单，我们把各种情况列出来，总能找到答案，因为一共就只有五个数字。
那换一个数字呢，比如20，你会发现，从递推的角度去思考很难得出答案，我先说2 然后…后面有非常多中情况 ，规则虽然很简单，但是这个思路确实不太行得通。此时递归的思路就来了，递归的思路是这个样子的：
-（1）我要是最后必须喊20，就必须让对手喊19或18。
-（2）我只要喊17，就可以让对手喊19或18，至于要倒数第二次喊17就行。
-（3）一次类推，只要我想喊17，上一次就必须是14，在上一次我就是11，以此类推 8 ，5，2
-（4）最后的结论就是只要我先喊2，然后依次5，8，11，14，17，20，我就必胜。
而这个思想就是一个递归的思想，递归的思想有两个明显的妙用：
-（1）只要解决了上一步的问题就能解决下一步的问题，一依次类推就能解决全部的问题。
-（2）推倒的过程是相同的，是可以复制的。
但是，使用递归一定要注意，过程相同，单要有结束条件。
规律： 倒着数，每次减3，最后的结果是2或1时停止：
我们可以下面代码：
public class Game { public static void main(String[] args) { List<Integer> five = getFive(20, new ArrayList<>()); System.out.println(five); } private static List<Integer> getFive(int num,List<Integer> res){ if (num > 0) { res.add(num); getFive(num - 3, res); } return res; } }
结果如下：
三、上台阶问题
一个人上台阶，每次只能上1个或2个台阶，问，有多少种情况可以上到第20个台阶？这个问题其实是斐波那契数列的应用。
前提条件是每次只能上一个或两个台阶，我们要上第20个台阶不外乎就是从第十八个或者第十九个台阶上，也就意味着上第十八个台阶的方式的数量+上第19个台阶的数量之和。
说的简单一点就是，我有x种情况可以上到第18个台阶，我有y种情况可以上到第19个台阶，那么上到第20个台阶的情况就有x+y种。
公式还是：f(n)=f(n-1)+f(n-2)。
