递归

一、递归

　　1、递归应用场景

　　　　递归的实际应用场景，迷宫问题（回溯），递归（Recursion）

　　2、递归的概念

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

　　3、递归调用机制

　　　　递归调用机制，常见应用：

　　　　（1）打印问题

1 public static void test(int n) {
2     if (n > 2) {
3     　　test(n - 1);
4      }
5     System.out.println("n=" + n);
6 }

　　　　（2）阶乘问题

1 //阶乘
2 public static int factorial(int n) {
3     if (n == 1) {
4         return 1;
5     } else {
6        return factorial(n - 1) * n;   // 1*2*3
7     }
8 }
9

　　　　图解：

　　4、递归能解决的问题

　　　　（1）各种数学问题如：八皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题

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

　　　　（3）将用栈解决的问题—>递归代码比较简洁

　　5、递归需要遵守的重要规则

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

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

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

　　　　（4）递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError

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

递归