[关闭]
@HUST-SuWB 2018-04-22T10:19:16.000000Z 字数 2261 阅读 422

从八皇后问题看递归的函数调用链

Finlabtech

八皇后问题

如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后的解法

八皇后问题是回溯算法的典型案例。

  1. /**
  2.  * @author: tianxie
  3.  * @Description: 八皇后问题
  4.  * @See: https://www.cnblogs.com/newflydd/p/5091646.html
  5.  * @Date: 2018/4/13下午4:21
  6.  */
  7. public class EightQueen {
  9.     //使用常量来定义，方便之后解N皇后问题
  10.     private static final short N=9;
  11.     //结果计数器
  12.     private static int count=0;
  14.     public static void main(String[] args) {
  15.         Long start = System.nanoTime();
  16.         //初始化棋盘，全部置0
  17.         short chess[][] = new short[N][N];
  18.         for(int i=0;i<N;i++){
  19.             for(int j=0;j<N;j++){
  20.                 chess[i][j] = 0;
  21.             }
  22.         }
  23.         putQueenAtRow(chess, 0);
  24.         System.out.println("解决 " + N + " 皇后问题，用时：" + (System.nanoTime() - start)/1000000 + "毫秒，计算结果："+count);
  25.     }
  27.     private static void putQueenAtRow(short[][] chess, int row) {
  28.         /**
  29.          * 递归终止判断：如果row==N，则说明已经成功摆放了8个皇后
  30.          * 输出结果，终止递归
  31.          */
  32.         if(row==N){
  33.             count++;
  34.             System.out.println("第 "+ count +" 种解：");
  35.             for(int i=0;i<N;i++){
  36.                 for(int j=0;j<N;j++){
  37.                     System.out.print(chess[i][j]+" ");
  38.                 }
  39.                 System.out.println();
  40.             }
  41.             return;
  42.         }
  44.         short[][] chessTemp=chess.clone();
  46.         /**
  47.          * 向这一行的每一个位置尝试排放皇后
  48.          * 然后检测状态，如果安全则继续执行递归函数摆放下一行皇后
  49.          */
  50.         for(int i=0;i<N;i++){
  51.             //摆放这一行的皇后，之前要清掉所有这一行摆放的记录，防止污染棋盘
  52.             for(int j=0;j<N;j++)
  53.                 chessTemp[row][j]=0;
  55.             chessTemp[row][i]=1;
  57.             if( isSafety( chessTemp,row,i ) ){
  58.                 putQueenAtRow(chessTemp,row+1);
  59.             }
  60.         }
  61.     }
  63.     private static boolean isSafety(short[][] chess,int row,int col) {
  64.         //TODO 为啥这里要定义一个初始值是1的step
  65.         int step=1;
  66.         //判断中上、左上、右上是否安全
  67.         while(row-step>=0){
  68.             //中上
  69.             if(chess[row-step][col]==1)
  70.                 return false;
  71.             //左上
  72.             if(col-step>=0 && chess[row-step][col-step]==1)
  73.                 return false;
  74.             //右上
  75.             if(col+step<N && chess[row-step][col+step]==1)
  76.                 return false;
  78.             step++;
  79.         }
  80.         return true;
  81.     }
  82. }

递归过程分析

  1. 栈帧(Stack Frame)是用于支持虚拟机进行方法调用和方法执行的数据结构，它是虚拟机运行时数据区的虚拟机栈(Virtual Machine Stack)的栈元素。栈帧存储了方法的局部变量表，操作数栈，动态连接和方法返回地址等信息。第一个方法从调用开始到执行完成，就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。
  2. 每一个栈帧都包括了局部变量表，操作数栈，动态连接，方法返回地址和一些额外的附加信息。在编译代码的时候，栈帧中需要多大的局部变量表，多深的操作数栈都已经完全确定了，并且写入到了方法表的Code属性中，因此一个栈帧需要分配多少内存，不会受到程序运行期变量数据的影响，而仅仅取决于具体虚拟机的实现。
  3. 一个线程中的方法调用链可能会很长，很多方法都同时处理执行状态。对于执行引擎来讲，活动线程中，只有虚拟机栈顶的栈帧才是有效的，称为当前栈帧(Current Stack Frame)，这个栈帧所关联的方法称为当前方法(Current Method)。执行引用所运行的所有字节码指令都只针对当前栈帧进行操作。
  4. 递归之所以能实现，就是因为函数的每个执行过程都在栈中有自己的形参和局部变量的复制，这些复制和函数的其他执行过程毫不相干。这种机制是大多数程序设计语言实现子程序的基础，使得递归成为可能。假定某个主调函数调用了一个被调用函数，在假定被调用函数又反过来调用主调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的主调用函数、现在的被调用函数在栈中较低的位置，有它独立的一组参数和自变量，原先的参数变量将不受影响，所以递归能正常工作。

当你单步调试上面的八皇后示例代码时，能清晰的感受到递归时函数调用不断入栈出栈的过程。

扩展阅读

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注