前言
本文为 【数据结构与算法】 递归算法 相关知识，下边将对斐波那契数列、抢5游戏，上台阶问题，汉诺塔问题，树和图的遍历等递归问题进行介绍，帮助大家理解递归算法~
📌博主主页：小新要变强的主页
👉Java全栈学习路线可参考：【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引，内含最全Java全栈学习技术清单~
👉算法刷题路线可参考：算法刷题路线总结与相关资料分享，内含最详尽的算法刷题路线指南及相关资料分享~
👉Java微服务开源项目可参考：企业级Java微服务开源项目（开源框架，用于学习、毕设、公司项目、私活等，减少开发工作，让您只关注业务！）
目录
学习递归之前，我们可以首先思考一下“递推”这个概念？
因为，人的思想是更适合 【递推】 而不是 【递归】。
一、斐波那契数列
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 f(n)=\begin{cases} 1,n=1,2\ f(n-1)+f(n-2),n>2 \end{cases} 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)。
四、汉诺塔问题
传说越南河内有一个寺庙，寺庙里有三根柱子，憎侣之间传言如果按照某个规定将64个盘子全部移动另外的柱子上，世界末日也就到了。事实证明，如果僧侣每一秒移动一个，大概需要5800亿年，当然这只是一个传说，这也是汉诺塔（Hanoi就是河内的意思）。
汉诺塔问题的描述：有三个柱子A、B、C，现在有n个盘子，需要从A柱转移到C柱，需要满足一下条件：
- （1）每次只能移动一个盘子
- （2）任何时候小盘子不能放在大盘子下边
- （3）B柱可以用来零时存放盘子，但是依然要满足小盘子不能放在大盘子下边的条件
其实，这个游戏我们小时候都玩过，如果只有三个盘子这个游戏是很简单的，但是盘子数量一旦多起来就不是很好处理了：
我们以三个盘子为例，我们不妨简单的玩一下：
- 第一步
- 第二步
- 第三步
- 第四步
- 第五步
- 第六步
- 第七步
对于三个盘子的汉诺塔来说，还是比较简答的，但是盘子的数量如果增加一杯呢？
如果从递推的角度去思考这个问题，一定要理性的分析一下这个过程中的规律，才能下结论。
但是如果思维反转，用递归来思考呢？
我们要实现64个盘子的汉诺塔，那么要让63个的变成一个什么样子呢？
我们要做的就是将前63个移动到B柱，将第64个从A移动到C，此时最大号的盘子就转移成功了：
然后我们再将B柱的所有盘子移动到C柱就好了。
通过这个问题，我们巧妙的将大的问题抽象成一个统一可复制的算法，而计算机最大的优势就在于快速的做出大量的重复性问题。
public class Hanoi {
public static void main(String[] args) {
hanoi(3,'A','B','C');
}
/**
* 解决n层汉诺塔问题的方法
* @param num 盘子的数量
* @param from 第1根柱子
* @param temp 第2根柱子
* @param to 第3根柱子
*/
public static void hanoi(int num,char from, char temp,char to){
if(num < 1){
System.out.println("您输入的数字不合法！");
}
if (num == 1){
System.out.println("将【"+ num +"】个盘子从【"+from+"】转移到【"+to+"】");
} else {
//要解决n层汉诺塔的问题，可以将n个盘子分解成（n-1） 1
// 1、先处理n-1个盘子的汉诺塔问题，从from转移到temp，
hanoi(num-1,from,to,temp);
// 2、挪动盘子
System.out.println("将【"+ num +"】个盘子从【"+from+"】转移到【"+to+"】");
// 3、再处理一次n-1个盘子的汉诺塔问题，从temp转移到to，
hanoi(num-1,temp,from,to);
}
}
}
时间复杂度的计算：
用递归来解决汉诺塔问题是非常方便的选择，最后我们来分析一下汉诺塔问题的时间复杂度。 我们很容易得到汉诺塔问题的递推公式，64层汉诺塔，需要将63层的汉诺塔在A和B之间转换两次+最大的盘子移动一次： f ( n ) = { 1 , n = 1 2 f ( n − 1 ) + 1 , n > 1 f(n)=\begin{cases} 1,n=1\ 2f(n-1)+1,n>1 \end{cases} \ f(n)={1,n=1 2f(n−1)+1,n>1
计算过程：
f ( n ) = 2 f ( n − 1 ) + 1 = 2 ∗ （ 2 f ( n − 2 ) + 1 ） + 1 = 2 ∗ 2 f ( n − 2 ) + 3 = 2 （ n − 1 ） + ( 1 + 3 + 7 + . . . ) = 2 n − 1 f(n)=2f(n-1)+1 = 2*（2f(n-2)+1） + 1 = 2*2f(n-2) + 3 = 2^（n-1） + (1 + 3 + 7 + ...) = 2^n - 1 f(n)=2f(n−1)+1=2∗（2f(n−2)+1）+1=2∗2f(n−2)+3=2（n−1）+(1+3+7+...)=2n−1
舍掉常数项，所以汉诺塔问题的时间复杂度为O(2^n)。
五、树和图的遍历
树的遍历，其实本质也是一种递归：
public class RecursiveBinaryTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
// 先序打印所有节点
public static void Preorder(Node root) {
if (root == null) {
return;
}
System.out.println(root.value);
Preorder(root.left);
Preorder(root.right);
}
public static void Inorder(Node root) {
if (root == null) {
return;
}
Inorder(root.left);
System.out.println(root.value);
Inorder(root.right);
}
public static void Postorder(Node root) {
if (root == null) {
return;
}
Postorder(root.left);
Postorder(root.right);
System.out.println(root.value);
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
Preorder(root);
System.out.println("====先序遍历====");
Inorder(root);
System.out.println("====中序遍历====");
Postorder(root);
System.out.println("====后续遍历====");
}
}
使用递归对图进行深度优先遍历，它的结构和之前的栈可能有些不同：
// 使用递归遍历图
public static <T> void recursive(Vertex<T> vertex){
// 拿到顶点进行遍历操作
if(!vertex.visited){
System.out.println(vertex.t);
vertex.visited = true;
}
// 看看当前的顶点时候有邻接节点，如果有执行相同错做
if(vertex.neighborList != null){
for (Vertex<T> tVertex : vertex.neighborList) {
recursive(tVertex);
}
}
}
后记
👉Java全栈学习路线可参考：【Java全栈学习路线】最全的Java学习路线及知识清单，Java自学方向指引，内含最全Java全栈学习技术清单~
👉算法刷题路线可参考：算法刷题路线总结与相关资料分享，内含最详尽的算法刷题路线指南及相关资料分享~
👉Java微服务开源项目可参考：企业级Java微服务开源项目（开源框架，用于学习、毕设、公司项目、私活等，减少开发工作，让您只关注业务！）