【说明】：
本文是左程云老师所著的《程序员面试代码指南》第一章中“用栈来实现汉诺塔问题”这一题目的C++递归方法复现。
本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】：
题目再重述一遍：
汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而必须经过中间。求当有N层塔的时候，打印最优移动过程和最优移动总步数。
例如，当塔为两层时，最上层的塔记录为1，最下层的塔记录为2，则打印：
move 1 from left to mid
move 1 from mid to right
move 2 from left to mid
move 1 from right to mid
move 1 from mid to left
move 2 from mid to right
move 1 from left to mid
move 1 from mid to right
It will move 8 steps.
【思路】：
递归的终止条件：汉诺塔只剩一层的时候。
对于普通的汉诺塔问题来说，递归的思路为：将n-1个盘子从A移到B，把最下面个移到C，然后把N-2个从B移到A，第N-1个移到C，如此继续下去。
对于本文所述的汉诺塔问题，递归思路差不多，读者可参考左老师的书，或者直接从我写的代码猜测。
【编译环境】：
CentOS6.7（x86_64）
gcc 4.4.7
【实现】：
实现及测试代码：
/* *文件名：limithannoi_recursion.cpp *作者： *摘要：使用递归的方法实现增加限制后的汉诺塔问题 */#include#include using namespace std;int hanoiRec(int layer,string src,string dst){ if(1 > layer) return 0; if(1 == layer) //只有一层时（递归的退出检测） { if("mid" == src || "mid" == dst) //源端或目的端为中间的情况 { cout << "move 1 form " << src << " to " << dst << endl; return 1; } else //源端或目的端为非中间的情况（左/右） { cout << "move 1 form " << src << " to mid" << endl; cout << "move 1 form mid to " << dst << endl; return 2; } } //有多层的情况 if("mid" == src || "mid" == dst) //源端或目的端为mid的情况(普通的汉诺塔问题) { //获得辅助端（左/右） string aux = ("left" == src || "left" == dst) ? "right" : "left"; //第一步，将1～layer-1层从源端移动到辅助端 int step1 = hanoiRec(layer-1,src,aux); //第二步，将第layer层移动到目的端 int step2 = 1; cout << "move " << layer << " from " << src << " to " << aux << endl; //第三步，将1～layer-1层从辅助端移动到目的端 int step3 = hanoiRec(layer-1,aux,dst); return step1 + step2 + step3; } else //源端和目的端为非mid的情况 { //第一步，将1～layer-1层从源端移动到目的端 int step1 = hanoiRec(layer-1,src,dst); //第二步，将第layer层从源端移动到mid端（即mid端为辅助端） int step2 = 1; cout << "move " << layer << " from " << src << " to mid" << endl; //第三步，将1～layer-1层从目的端移动到源端 int step3 = hanoiRec(layer-1,dst,src); //第四步，将第layer层从mid端移动到目的端 int step4 = 1; cout << "move " << layer << " from mid to " << dst << endl; //第五步，将1～layer-1层从源端移动到目的端 int step5 = hanoiRec(layer-1,src,dst); return step1 + step2 + step3 +step4 + step5; }}int main(){ int step = hanoiRec(2,"left","right"); cout << "It will move " << step << " steps." << endl; return 0;}
【一点想说的】：
陈丹青先生在优酷中有一个名为的艺术节目，在第一季（目前只有一季）第四集《初习的作品》中，陈丹青先生提到这么一个事情：有一位朋友去他家做客时，就挨个的欣赏挂在他家墙上的画，每一幅停留的时间都不长，知道走到梵高的这一个小的未完成的人物画像前，陈丹青先生的朋友驻足良久，说到：“我操，真他妈好看！”。
我想说的是：“我操，递归这种思想真他妈神奇。”
^_^ ^_^ ^_^
注：
转载请注明出处；
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。