递归与回溯

递归

递归中最熟悉的当然是最经典的汉诺塔问题：

#include <iostream>
using namespace std;

void Hanoi(int n, char src, char mid, char dest)
{
	if (n == 1)
	{
		cout << src << "->" << dest << endl;
		return;
	}
    //先将n-1个盘子从起点（src）借助中点（mid）移动到中转处（mid）
	Hanoi(n-1, src, dest, mid);
    //再将“最大的盘子”移动到目的地
	cout << src << "->" << dest << endl;
    //最后将n-1个盘子从中转处（mid）借助起点（src）移动到目的地（dest）
	Hanoi(n-1, mid, src, dest);
	return;

}

int main()
{
    cout << "Please enetr the number of the towers" << endl;
	int n;
	cin >> n;
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

回溯

回溯算法详解