内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

6.1递归应用场景

看一个实际应用场景，迷宫问题(回溯)，递归(recursion)

6.2递归的概念

简单的说:递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

1.     打印问题

2.     阶乘问题

3.     使用图解的方式说明的递归的调用机制

4.     代码演示

6.4递归能解决什么样的问题

递归用于解决什么样的问题

1.      各种数学问题如:8皇后问题﹐汉诺塔，阶乘问题,迷宫问题,球和篮子的问题(google编程大赛)

2.      各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.

3.      将用栈解决的问题-->第归代码比较简洁

6.5递归需要遵守的重要规则

1.      执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

2.      方法的局部变量是独立的，不会相互影响,比如n变量

3.      如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.

4.      递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)

5.      当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

6.6递归-迷宫问题

6.6.1迷宫问题

6.6.2代码实现

6.6.3对迷宫问题的讨论

1.      小球得到的路径，和程序员设置的找路策略有关即:找路的上下左右的顺序相关

2.      在得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化

3.      测试回溯现象

4.      思考:如何求出最短路径?思路->代码实现

思路：设计一个数组用数组表示不同的策略用for把策略走一遍，将每一个节点的2保存到一个集合中，看哪个集合的大小是最小的