跳到主要内容

九：学习递归。递归的经典实例：打印问题、阶乘问题、递归-迷宫问题、八皇后问题

前言​

  • 先说一下递归算法的重要性，后面的快速排序、归并排序都会用到递归。可见其重要性
  • 这里学的时候，自我感觉有点难，逻辑有点混乱，可以先学习一遍，然后到了后面用到的时候，再来学习一遍。

一、递归​

2.1 递归简单介绍​

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

2.2 重要规则​

1、 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)；
2、 方法的局部变量是独立的，不会相互影响,比如n变量；
3、 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.；
4、 递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了；

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

2.3 递归形式​

递归就是函数调用自己本身，但是要加上 必须的条件，以免变成 死龟

形式如下

public void func(int n){
   
     
	if(condition){
   
     
		
	}
	func(n-1);
}

2.4 递归能解决的问题​

1、 各种数学问题如:8皇后问题,汉诺塔,阶乘问题,迷宫问题,球和篮子的问题(google编程大赛)；
2、 各种算法中也会使用到递归，比如**快排，归并排序，二分查找，分治算法**等.；
3、 将用栈解决的问题–>第归代码比较简洁；

二、打印问题​

2.1 介绍​

通过打印来了解递归

2.2 代码​

/**
 * 打印问题.
 * 当 n 为 4时 输出的顺序：n=2 n=3 n=4
 * @param n
 */
 public static void test01(int n) {
   
     
    if (n > 2) {
   
     
        test01(n - 1);   // 如果为 + 时，会成为 栈溢出，报错：java.lang.StackOverflowError
    }
    System.out.println("n=" + n);
}