数据结构之递归

 

 

    递归（recursion）是指在定义自身的同时又出现了对自身的引用。如果一个算法直接或间接地调用自己，则称这个算法是一个递归算法。

    任何一个有意义的递归算法总是由两部分组成：递归调用与递归终止条件。

 

 /**
 * 阶汉诺塔问题可以描述为：假设有X、Y、Z 三个塔座，初始时有n 个大小不一的
 * 盘子按照从小到大的次序放在塔座X 上。现在要求将塔座X 上的所有盘子移动到塔座Z 上
 * 并保持原来的顺序，在移动过程中要满足以下要求：在塔座之间一次只能移动一个盘子并且
 * 任何时候大盘子都不能放到小盘子上。
 */
public static void hanio (int n, char x, char y, char z) {
	if (n == 1) 
		move( x, n, z);
	else {
		hanio (n - 1, x, z, y);
		move(x, n, z);
		hanio(n - 1, y, x, z);
	}
}
private static void move(char x, int n, char y) {
	System.out.println ("Move " + n + " from " + x + " to " + y);
}

 

 

     堆栈实现：

/**
 * 求解从迷宫中的起点到某个终点的路径
 */
public class Maze {

	public static void mazeExit(char[][] maze, int sx, int sy, int ex, int ey) {
		Cell[][] cells = createMaze(maze); //创建化迷宫
		printMaze(cells); //打印迷宫
		Stack s = new StackArray(); //构造堆栈
		Cell startCell = cells[sx][sy]; //起点
		Cell endCell = cells[ex][ey]; //终点
		s.push(startCell); //起点入栈
		startCell.visited = true; //标记起点已被访问
		while (!s.isEmpty()) {
			Cell current = (Cell)s.peek();
			if (current == endCell){ //路径找到
				System.out.println("共有" + s.getSize() + "步");
				while(!s.isEmpty()){
					
					Cell cell = (Cell)s.pop();//沿路返回将路径上的单元设为*
					cell.c = '*';
					//堆栈中与cell 相邻的单元才是路径的组成部分，除此之外，
					//堆栈中还有记录下来但是未继续向下探索的单元，
					//这些单元直接出栈
					while(!s.isEmpty() && !isAdjoinCell((Cell)s.peek(), cell))
						s.pop();
				}
				System.out.println("找到从起点到终点的路径。");
				printMaze(cells);
				return;
			} else { //如果当前位置不是终点
				int x = current.x;
				int y = current.y;
				int count = 0;
				if(isValidWayCell(cells[x + 1][y])){ //向下
					s.push(cells[x + 1][y]); cells[x+1][y].visited = true; count++;}
				if(isValidWayCell(cells[x][y + 1])){ //向右
					s.push(cells[x][y + 1]); cells[x][y + 1].visited = true; count++;}
				if(isValidWayCell(cells[x - 1][y])){ //向上
					s.push(cells[x - 1][y]); cells[x - 1][y].visited = true; count++;}
				if(isValidWayCell(cells[x][y - 1])){ //向左
					s.push(cells[x][y - 1]); cells[x][y - 1].visited = true; count++;}
				if (count == 0) s.pop();//如果是死点，出栈
			}//end of if
		}//end of while

		System.out.println("没有从起点到终点的路径。");
	}
	private static void printMaze(Cell[][] cells) {
		for (int x = 0; x < cells.length; x++){
			for (int y = 0; y < cells[x].length; y++)
				System.out.print(cells[x][y].c + " ");
			System.out.println();
		}
	}
	private static boolean isAdjoinCell(Cell cell1, Cell cell2) {
		if (cell1.x == cell2.x && Math.abs(cell1.y - cell2.y) < 2) return true;
		if (cell1.y == cell2.y && Math.abs(cell1.x - cell2.x) < 2) return true;
		return false;
	}
	private static boolean isValidWayCell(Cell cell) {
		return cell.c == '0' && !cell.visited;
	}
	private static Cell[][] createMaze(char[][] maze) {
		Cell[][] cells = new Cell[maze.length][];
		for (int x = 0; x < maze.length; x++) {
			char[] row = maze[x];
			cells[x] = new Cell[row.length];
			for (int y = 0; y < row.length; y++)
				cells[x][y] = new Cell(x, y, maze[x][y], false);
		}
		return cells;
	}
	public static void main(String[] args) {
		char[][] maze = {
				{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
				{'1', '0', '0', '1', '1', '1', '0', '0', '1', '1'},
				{'1', '0', '0', '1', '1', '0', '0', '1', '0', '1'},
				{'1', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
				{'1', '0', '0', '0', '0', '1', '1', '0', '0', '1'},
				{'1', '0', '0', '1', '1', '1', '0', '0', '0', '1'},
				{'1', '0', '0', '0', '0', '1', '0', '1', '0', '1'},
				{'1', '0', '1', '1', '0', '0', '0', '0', '0', '1'},
				{'1', '1', '0', '0', '0', '0', '1', '0', '0', '1'},
				{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
		};
		mazeExit(maze, 1, 1, 2, 8);
	}

}
class Cell {
	int x = 0; //单元所在行
	int y = 0; //单元所在列
	boolean visited = false; //是否访问过
	char c = ' '; //是墙('1')、可通路('0')或起点到终点的路径('*')
	public Cell(int x, int y, char c, boolean visited) {
			this.x = x; this.y = y;
			this.c = c; this.visited = visited;
	}
}