概述#

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

递归重要规则#

  1. 执行一个方法时，就创建一个新的受保护的独立空间（栈空间）。
  2. 方法的局部变量是独立的，不会相互影响，比如n变量。
  3. 如果方法中使用的是引用类型变量（比如数组，对象），就会共享该引用类型的数据。
  4. 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError。
  5. 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

练习#

  1. 请使用递归的方式求出斐波那契数1，1，2，3，5，8，13.…给你一个整数n，求出它的值是多少？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public class RecursionExercise01 {
    	public static void main(String[] args) {
    		T t = new T();
    		int n = 7;
    		int res = t.fibonacci(n);
    		if (res != -1) {
    			System.out.println("当 n=" + n + " 对应的斐波那契数=" + res);
    		}
    	}
    }

    class T {
    	public int fibonacci(int n) {
    		if (n >= 1) {
    			if (n == 1 || n == 2) {
    				return 1;
    			} else {
    				return fibonacci(n - 1) + fibonacci(n - 2);
    			}
    		} else {
    			System.out.println("要求输入的 n>=1 的整数");
    			return -1;
    		}
    	}
    }

  2. 猴子吃桃子问题：有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时（即还没吃）发现只有1个桃子了。问题：最初共多少个桃子？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public class RecursionExercise02 {
    	public static void main(String[] args) {
    		T t = new T();
    		int day = 10;
    		int peachNum = t.peach(day);
    		if (peachNum != -1) {
    			System.out.println("第 " + day + "天有" + peachNum + "个桃子");
    		}
    	}
    }

    class T {
    	public int peach(int day) {
    		if (day == 10) {
    			return 1;
    		} else if (day >= 1 && day <= 9) {
    			return (peach(day + 1) + 1) * 2;
    		} else {
    			System.out.println("day 在 1-10");
    			return -1;
    		}
    	}
    }

小老鼠出迷宫#

map1

map2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class MiGong {
	// 编写一个main方法
	public static void main(String[] args) {
		// 思路
		// 1. 先创建迷宫，用二维数组表示 int[][] map = new int[8][7];
		// 2. 先规定 map 数组的元素值: 0 表示可以走 1 表示障碍物
		int[][] map = new int[8][7];
		// 3. 将最上面的一行和最下面的一行，全部设置为1
		for (int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		// 4.将最右面的一列和最左面的一列，全部设置为1
		for (int i = 0; i < 8; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		map[3][1] = 1;
		map[3][2] = 1;
		map[2][2] = 1; // 测试回溯
		// 输出当前的地图
		System.out.println("=====当前地图情况======");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");// 输出一行
			}
			System.out.println();
		}
		// 使用findWay给老鼠找路
		T t = new T();
		// 下右上左
		t.findWay(map, 1, 1);
		System.out.println("\n====找路的情况如下=====");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");// 输出一行
			}
			System.out.println();
		}
	}
}

class T {
	// 使用递归回溯的思想来解决老鼠出迷宫
	// 老韩解读
	// 1. findWay方法就是专门来找出迷宫的路径
	// 2. 如果找到，就返回 true ,否则返回false
	// 3. map 就是二维数组，即表示迷宫
	// 4. i,j 就是老鼠的位置，初始化的位置为(1,1)
	// 5. 因为我们是递归的找路，所以我先规定 map数组的各个值的含义
	// 0 表示可以走 1 表示障碍物 2 表示可以走 3 表示走过，但是走不通是死路
	// 6. 当map[6][5] =2 就说明找到通路,就可以结束，否则就继续找.
	// 7. 先确定老鼠找路策略 下->右->上->左
	public boolean findWay(int[][] map, int i, int j) {
		if (map[6][5] == 2) {// 说明已经找到
			return true;
		} else {
			if (map[i][j] == 0) {// 当前这个位置0,说明表示可以走
				// 我们假定可以走通
				map[i][j] = 2;
				// 使用找路策略，来确定该位置是否真的可以走通
				// 下->右->上->左
				if (findWay(map, i + 1, j)) {// 先走下
					return true;
				} else if (findWay(map, i, j + 1)) {// 右
					return true;
				} else if (findWay(map, i - 1, j)) {// 上
					return true;
				} else if (findWay(map, i, j - 1)) {// 左
					return true;
				} else {
					map[i][j] = 3;
					return false;
				}
			} else { // map[i][j] = 1,2,3
				return false;
			}
		}
	}
}

汉诺塔#

Tower

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class HanoiTower { 
	//编写一个main方法
	public static void main(String[] args) {
		Tower tower = new Tower();
		tower.move(8, 'A', 'B', 'C');
	}
}
class Tower {
	//方法
	//num 表示要移动的个数, a, b, c 分别表示A塔，B 塔, C 塔
	public void move(int num , char a, char b ,char c) {
		//如果只有一个盘 num = 1
		if(num == 1) {
			System.out.println(a + "->" + c);
		} else {
			//如果有多个盘，可以看成两个 , 最下面的和上面的所有盘(num-1)
			//(1)先移动上面所有的盘到 b, 借助 c
			move(num - 1 , a, c, b);
			//(2)把最下面的这个盘，移动到 c
			System.out.println(a + "->" + c);
			//(3)再把 b塔的所有盘，移动到c ,借助a
			move(num - 1, b, a, c);
		}
	}
}

八皇后#