汉诺塔的递归解法

从维基百科上获取的c++代码

#include <iostream>
#include <cstdio>

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
    }
    else
    {
        hannoi (n-1, from, to, buffer);
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
        hannoi (n-1, buffer, from, to);
    }
}

int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
} 

输入4（即假设有4个圆盘）运行结果：

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

具体运行过程如下，为了方便将'A','B','C' 用A,B,C代替

 hannoi(4,A,B,C);  from = A,buffer = B,to = C    //入口
 hannoi(3,A,C,B);  from = A,buffer = B,to = C 
 hannoi(2,A,B,C);  from = A,buffer = B,to = C 
 hannoi(1,A,C,B);  from = A,buffer = C,to = B   //n = 1，向里递归结束

开始打印输出
-------------------------------------------------------------------------------
Move 1  A->B
Move 2  A->C     hannoi(1,B,A,C);  from = B,buffer = A,to = C  
Move 1  B->C 
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
Move 3  A->B     hannoi(2,C,A,B);  from = C,buffer = A,to = B
                           hannoi(1,C,B,A);  from = C,buffer = B,to = A 
Move 1  C->A    
Move 2  C->B     hannoi(1,A,C,B);  from = A,buffer = C,to = B
Move 1  A->B     
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
Move 4  A->C     hannoi(3,B,A,C);  from = B,buffer = A,to = C
                           hannoi(2,B,C,A);  from = B,buffer = C,to = A
                           hannoi(1,B,A,C);  from = B,buffer = A,to = C
Move 1  B->C     
Move 2  B->A     hannoi(1,C,B,A);  from = C,buffer = B,to = A
Move 1  C->A
Move 3  B->C     hannoi(2,A,B,C);  from = A,buffer = B,to = C
                           hannoi(1,A,C,B);  from = A,buffer = C,to = B
Move 1  A->B
Move 2  A->C     hannoi(1,B,A,C);  from = B,buffer = A,to = C  
Move 1  B->C                                                

以上是对代码运行过程的理解

-----------------------------------------------------快乐的分割线

以下是对如何写出该递归代码的理解

借鉴知乎上的一篇文章 侵删！点击即可跳转
在假设有n个圆盘的情况下，（从上到下1,2...n标号）
抽象成三个步骤

汉诺塔4盘移动图.jpg

结合代码分析：

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << from << " to " << to << endl;  
//如果只有一个盘子，则直接将其从A移动到C
    }
    else
    {
        hannoi (n-1, from, to, buffer);
//如果有n个盘子，将n-1个盘子从A移动到B，对应（b）
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
//此时将第n个盘子从A移动到C，对应（c）
        hannoi (n-1, buffer, from, to);
//再将B上的n-1个盘子从B移动到C,对应（d）
    }
}

递归的精神就是只管当前的任务，其他任务交给下一层去执行!
写递归算法的总结：
1.先把临界条件（结束该次递归的条件）写出
2.再把其他情况用调用自身的递归实现
其他的就不管了