tail recursion

函数在调用的时候，会提前创建一个栈空间，给传递的参数也分配空间，当函数结束返回上层函数的时候，一些局部变量需要从栈中弹出并恢复到调用子函数之前的值，返回到上一个函数调用子函数之前的现场。如果是尾递归，从子函数返回的时候这个函数同时也会结束了，所以没有必要恢复一些局部变量，直接把局部变量的栈空间删除。因此一个尾递归的函数根本不需要使用栈来给子函数变量空间，可以直接使用当前变量的值为新参数的值。

backtracking

八皇后问题

用一个类Queens表示棋盘上现在的皇后布局，solve_from()函数用来从一个当前的布局开始寻找解，整体思路如下：

solve_from(Queens configuration)    if 八皇后布局已经完成        print configuration    else        for 当前每个没有被皇后控制的格子{            在configuration中该格子上放一个皇后;            solve_from(configuration);            在configuration中将该皇后移除;        }

整个程序的思路就是首先输入棋盘的大小，如果是合理的输入则创建一个该大小的Queens类并用solve_from()函数寻找结果，如下：

int main() {	int board_size;	int max_board = 10;	print_configuration();	cout << "what is the size of the board?" << flush;	cin >> board_size;	if(board_size < 0 || board_size > max_board)		cout << "the size must between 0 and "  << max_board << endl;	else{		Queens configuration(board_size);		solve_from(configuration);	}	return 0;}

Queens类里面需要解决的问题是如何选择数据结构来存储当前皇后布局，这里选择了布尔类型二维数组来表示棋盘，count记录现在已经放上去的皇后数量，按照从上往下的顺序来放，也就是说count = k的时候上面k行都已经被皇后占领。还有以下需要用到的一些methods:

• bool unguarded(int col) const: 未被占领的第一行的col列位置是否被统治
• void insert(int col): 将一个皇后插入到未被占领的第一行的col位置,同时count++
• void remove(int col): 将被占领的最下面一行的皇后从col位置移除，同时count--
• bool is_solved() const: 皇后数量达到board_size则返回true;

类的基本数据结构如下：

const int MAX_BOARD = 30;class Queens {public:	int board_size;	bool unguarded(int col) const;	void insert(int col);	void remove(int col);	bool is_solved() const;	void print();private:	int count;//current number of queens	bool queen_square[MAX_BOARD][MAX_BOARD];	};

主要的几个函数：

Queens::Queens(int size){	board_size = size;	count = 0;	for (int row = 0; row < board_size; ++row) {		for (int col = 0; col < board_size; ++col) {			queen_square[row][col] = false;		}	}}void Queens::insert(int col){	queen_square[count++][col] = true;}bool Queens::unguarded(int col) const{	bool ok = true;	for (int i = 0; ok && i < count; ++i) {//检查col列上面是否有皇后		ok = !queen_square[i][col];	}	for (int i = 0; ok && count - i >= 0; ++i) {//检查左上方是否有皇后		ok = !queen_square[count - i][col - i];	}	for (int i = 0; count - i >= 0 && count + i < board_size; ++i) {//右上方		ok = !queen_square[count - i][col + i];	}	return ok;}

八皇后问题主要的方法就是回溯法，可以从某一个状态开始，尝试变换到下一个状态，然后从下一个状态开始求解，然后恢复到原来的状态再进行下一步尝试。

回溯法与八皇后问题