递归思想

引用写递归函数的正确思维方法其中关键的两句话

你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.
---Paul Graham

递归解决问题的思想有点类似数学归纳法或者递推公式，再次引用Paul Graham提到的一种思想

当n=0, 1的时候, 结果正确.
假设函数对于n是正确的, 函数对n+1结果也正确.
如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。
---Paul Graham

要告诉计算机处理到边界的时候应该怎么做，即问题分解到最小状态时如何解决和问题什么时候完成，第二件要做的事情就是告诉计算机在每一步如何处理问题。

下面先举两个例子，未完待续。

汉诺塔问题

设定：三根柱子ABC，其中一根放置了从小到大n个带孔的圆盘，目的是将这些圆盘最终放置到C柱子上（B柱做中转使用）。
规则：1.一次只能移动一个盘子。2.不能将盘子放在更小的盘子上。

思路：
n个盘子分解为从上到下的(n-1)个盘子和1个底部最大盘子，分为三步，将(n-1)个小盘子从A->B,（C中转），1个底部盘子从A->C（B中转），再将（n-1）个小盘子从B->C（A做中转）。（问题已经被分解了一层）。

上个步骤的第二步，将底部盘子从A通过B移到C，只需要直接A->C即可，这也是n=1汉诺塔问题的解，处理结束。

接着上一段的思路，问题被分解成了3个部分，其中第二个部分不需要额外处理，即可结束处理。第一步变成了处理（n-1）个小盘子从A->C->B的问题，第三步变成了处理（n-1）个小盘子从B->A->C的问题。此时原本从A->B->C的n个汉诺塔问题，转变成2个（n-1）的汉诺塔问题。

此时研究的对象转变为两个（n-1）的子问题，对这个子问题，继续采用分解的思路，化成两个（n-2）级别的问题，......以此类推，当变成处理两个1个圆盘的汉诺塔问题，问题全部解决，从最内层的操作开始，一步步执行即可完成n个汉诺塔问题。

在这个问题解题过程中，

问题分解到最小状态时如何解决和问题什么时候完成：n=1时完成，直接移动。
在每一步如何处理问题：分解成两个维数更低的汉诺塔问题。

引用郭炜老师在课堂上展示的代码并添加了一点点注释：

#include
using namespace std;

void Hanoi(int n, char src, char mid , char dest){
//将src座上的n个盘子，以mid座为中转，移动到dest座
	if (n==1){//只需要移动一个盘子
		cout<"<"<>n;//输入盘子数目
	Hanoi(n,'A','B','C');
	return 0;
} 

当n=3时的输出结果：

A->C
A->B
C->B
A->C
B->A
B->C
A->C

N皇后问题

N皇后问题可以看成时八皇后问题的拓展，八个元素的放置变成了n个元素，\(8*8\)的棋盘变成了\(n*n\)的棋盘。
规则：1.每个元素不能同行或者同列。2.每个元素不能在对角线上。

分析：1.每行上有一个元素，每列上也有一个元素。2.每个元素的横坐标和纵坐标的差值不能相等。

• 用每行上的列数表示位置，按顺序存放在数组中，则数组的下标表示行，数组存放的值表示当前行的皇后所在的列。

思路：从第0行开始排列，当第0行放好之后，考虑第1行，......，当第k-1行摆好之后，考察第k行摆法（解决办法），继续操作，知道第N-1行摆好，此时N个元素全部摆好。

在这个问题解题过程中，

问题分解到最小状态时如何解决和问题什么时候完成：摆完N个元素，将每行元素列的位置按顺序输出。
在每一步如何处理问题：对第k行的元素从第0列到第N列遍历，与之前已经已经确认好位置的k-1个位置遍历比较，如果不满足两点要求。则尝试第k行的元素可能的下一个位置，继续比对，如果对已经确认好位置的k-1个位置遍历完之后，均满足要求，那么这个点可以作为第k行元素的位置，继续启动第k+1行元素的搜寻过程，若k行寻找元素失败则会不返回值，但是此时对第k行元素位置的查找是由第k-1行程序调用的，不返回值，对k-1位置的查找将继续进行列遍历。某种幸运的情况，完成了N个元素的正确摆法，将触发输出，并往上层返回，再对上一层的位置继续查找，直到完成所有位置的搜寻。

对该问题，郭炜老师的示例解法属于，遇到当前行无解的情况，会返回上一行的位置，继续遍历。

引用郭炜老师在课堂上展示的代码并添加一点点注释：

#include
#include
using namespace std;
int N;
int queenPos[100];//用来存放算好的皇后位置，最左上角是（0，0） 
void NQueen(int k);
int main() 
{
	cin>>N;
	NQueen(0);//从第0行开始摆皇后 
	return 0;
}

void NQueen(int k){//在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后
	int i;
	if( k==N ){//N个皇后已经摆好 
		for( i=0;i

2 4 1 3
3 1 4 2