递归与回溯

递归：是调用一个和调用者同名的方法，他并不是一个方法调用自身，而是方法的一个实例调用相同方法的另一个实例。

递归分为：尾递归，非尾递归，间接递归以及过分递归；

相比于迭代，递归的效率低，但是递归的解决方案简单，与源算法逻辑一致性强，使用迭代需要定义一个新的数据结构实现堆栈，迭代应当适用在实时系统。

实例：斐波那契数列使用递归实现：

0，1，1，2，3，5，8， 13， 21， 34， 55， 89 ......

Fib(n) = n 当n < 2时；Fib(n) = Fib(n-2) + Fib(n-1) 其他情况；

在Java中可以直接定义一个函数Fib然后使用迭代实现：

    public int Fib(int n) {
        if(n < 2) {
            return n;
        }else {
            return Fib(n-2) + Fib(n-1);
        }
    }

这个方法简单易懂，但是效率极低，在计算第26个斐波那契数时，大约需要25万次的调用，计算第31个数时需要接近三百万个调用，代价很高。

在计算相对较小的数时可以采用递归，

在计算较大数据时可以采用迭代实现：

    public int iterativeFib(int n) {
        if(n < 2) {
            return n;
        }else { 
            int i = 2, temp, current = 1, last = 0;
            for(; i <= n;i++) {
                temp = current;
                current += last;
                last = temp;
            }
            return current;
        }
    }

回溯：从某点出发有很多的道路选择，但是不清楚那一条道路能有效地解决问题，尝试一条道路失败后，返回到岔路口再试另外的道路，我们必须确定所有的路都是可以尝试的，可以返回的。

一个经典的回溯问题：

八皇后问题：将八个皇后放在一个棋盘上，要求他们不能相互攻击，规则是一个皇后可以攻击同一行，同一列以及和他在同一条对角线上的任意皇后。

解决问题的伪代码：

putQueen(row)

　　for 同一row的每个位置col

　　if  col可用

　　　　把下一个皇后放在col上

　　if（row < 8)

　　　　putQueen(row+1)

　　else 成功；

　　取走col上的皇后

算法的java实现如下：

package queen;
import java.io.*;

public class Queens {
    static final int squares = 8, norm  = squares - 1;
    static final boolean available = true;
    static int [] positionInRow = new int[squares];
    static boolean [] column = new boolean[squares];
    static boolean [] leftDiagonal = new boolean[squares*2 -1];
    static boolean [] rightDiagonal = new boolean[squares*2 -1];
    static int howMany = 0;
    
    public Queens() {
        //初始化
        for(int i = 0;i < squares; i++) {
            positionInRow[i] = -1;
            column[i] = available;
        }
        for(int i = 0; i < squares*2 -1;i++) {
            leftDiagonal[i] = rightDiagonal[i] = available;
        }
    }
    static void printBorad(PrintStream out) {
        System.out.println("第"+howMany+"种摆放方式：");
        //循环打印可行解决方案q表示可行位置
        for(int i=0;i<squares;i++){
            for(int j=0;j<squares;j++){
                if(i == positionInRow[j]){
                    System.out.print("q ");
                }else
                    System.out.print("* ");
            }
            System.out.println();
        } 
    }
    
    static void PutQueen(int row) {
        for(int col = 0; col < squares;col++) {
            if(column[col] == available &&
                leftDiagonal[row+col] == available &&
                rightDiagonal[row - col +norm] == available) {
                //确认下一个可以放置的位置
                
                positionInRow[row] = col;
                
                //找到可放置位置后，确定不可行域
                column[col] = !available;
                leftDiagonal[row+col] = !available;
                rightDiagonal[row-col+norm] = !available;
                
                //遍历所有的行
                if(row < squares - 1) {
                    PutQueen(row+1);
                }else {
                    printBorad(System.out);
                    ++howMany;
                }
                //重置可行域
                column[col] = available;
                leftDiagonal[row+col] = available;
                rightDiagonal[row-col+norm] = available;
            }
        }
    }
    static public void main(String[] args) {
        Queens queens = new Queens();
        queens.PutQueen(0);
        System.out.println("There are " + howMany + " solutions for this problem!");
    }
}