递归算法之求解汉诺塔问题

2017/06/02

递归算法之求解汉诺塔问题

Java程序代码

import java.util.Scanner;

public class HanoiDemo {
	public static void main(String[] args) {
		long startTime = System.nanoTime();
		char a = 'A';
		char b = 'B';
		char c = 'C';
		System.out.print("请输入汉诺塔盘子数目:");
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		s.close();
		System.out.printf("%d个盘片的移动过程:\n", n);
		hanoi(n, a, b, c);
		
	static void hanoi(int n, char a, char b, char c) {
		if (n == 1) {
			System.out.printf("盘片%d: %c → %c\n", n, a, c);
		} else {
			hanoi(n - 1, a, c, b);
			System.out.printf("盘片%d: %c → %c\n", n, a, c);
			hanoi(n - 1, b, a, c);
		}
	}
}

运行截图

img

过程分析

递归将难求解的大问题不断分解为新的子问题,从未知向已知推进。这里以个人熟悉的Java虚拟机对方法的递归执行过程进行解释

1.首先为执行的移动的两条输出语句打上断点,方便观察每个递归方法执行的过程

img

2.Debug主程序并且输入盘子数目为4,可以观察到执行到第一次断点时,线程的方法栈中除了主方法对应的栈帧外,还有四个栈帧,是由递归调用hanoi(n - 1, a, c, b);产生的,并且每次递归调用时参数都在改变,此时方法栈情况如图所示。

img

3.继续执行程序,能够得到hanoi(1,a,c,b)的解。该方法对应的栈帧出栈,此时可以看到控制台输出第一次盘片移动过程

img img

4.继续执行程序System.**out**.printf("盘片%d: %c → %c\n", n, a, c);,控制台输出第二次盘片移动过程,这里打印语句模拟的是一次移动一个盘片的过程。程序执行到hanoi(n - 1, b, a, c); `有会有新的栈帧入栈

img img

5.继续执行程序,可以看到输出第三次盘片移动的过程,并且方法 hanoi(1,b,a,c) 和 hanoi(2,a,b,c) 对应的栈帧出栈,因为 hanoi(2,a,b,c) 方法的子方法为 hanoi(1,a,c,b) 和 hanoi(1,b,a,c),能够直接求出移动过程

img img

6.继续执行程序,可以看到输出第四次盘片移动过程,并且方法hanoi(3,a,c,b) 创建了两个新的栈帧

img img

7.篇幅原因,省略往下继续执行的过程。从每步执行结果可以得知,Java虚拟机是通过虚拟机中的栈帧不断入栈和出栈来执行递归的方法。每当方法执行到递归出口时,就将该方法栈帧出栈,并且打印移动过程。当方法需要分解为子方法时,就为子方法创建相应个数的栈帧,并且子方法的栈帧位于父方法对应的栈帧之上。所以在方法栈的入栈和出栈过程中,完成了对大问题的逐步分解求解过程。但是,递归内存消耗很大。而且,如果递归深度太大,会导致栈深度超出虚拟机所允许的最大深度,抛出StackOverflowError异常!!此时可以调整虚拟机栈内存(-Xss参数)的大小来加深栈的深度。

8.比如计算999个盘片的汉诺塔过程,如下图程序执行开始就会在方法栈中会创建1000个栈帧(其中一个为主方法对应的栈帧),程序继续执行的过程中为了保留子方法的现场,请求的栈深度还会不断加深,最终超出虚拟机允许的最大深度。

使用递归虽然可以简化思维过程,效率和开销问题是递归最大的缺点。但是不可否认递归对解描述的直观性以及代码的简洁性,所以了解递归算法的过程,对递归算法的把握及使用场合的选择有重要意义!!!

img

10.下图是4个盘片移动的方法回调步骤,便于分析整个求解过程。

img

Post Directory