递归——汉诺塔问题

引:递归求阶乘

用递归算法求n!
定义函数fact(n) = n!
则有fact(n) = n*fact(n-1)
已知fact(1) = 1

为了表达得更直观清晰，定义两个结点：“或结点”和“与结点”。
1. 或结点如图9.1所示，图中A为“或结点”，A依据不同的条件会有两个不同的取值B或C。

2. 与结点如图9.3所示，与结点要涂黑，相关联的B与C之间要用弧线练起来。A为与结点，A的最终取值为C结点的值，但为了求得C的值，得先求出B结点的值，C时B的函数。仍以求n!为例画出如图9.4所示的与或图。

• 图9.4中，A为或结点；B为直接可解结点，值为1（直接可解结点用圆圈中加一个黑点表示）；C为与结点，当n>1时，A的取值即C的值，而C的值即E的值，为了求得E的值，需要先求出D的值。D值fact(n-1)乘以n即为E的值。

• 与结点可能有多个相关联的点，这时可描述为图9.5。图9.5中A结点的值最终为D的值，但为了求D，需先求B和C。从图上看，先求左边的点才能求最右边的点的值，我们约定最右边D点的值就是A结点的值。

下面以3！为例来画与或结点图，目的是体会递归的含义，见图9.6。

图9.7画出了调用和返回的递归示意图。

图9.8为程序框图

总结：递归过程相当于从菜心“推到”外层，但递归算法的出发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。

---

汉诺（hanoi）塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

思路：
先从简单的情况分析起：

• 在A柱只有一只盘子，这时只需将该盘从A搬至C，一次完成，记为move 1 from A to C。
• 在A柱上有两只盘子，1为小盘，2为大盘（1在2上面）。
  
  1. 将1号盘从A移至B，这是为了让2号盘能移动，记为move 1 from A to B。
  2. 将2号盘从A移至C，记为move 2 from A to C。
  3. 再将1号盘从B移至C，记为move 1 from B to C。
• 在A柱上有3只盘子，从小到大从上到下分别为1号、2号、3号。
  
  1. 将1号盘和2号盘视为一个整体，先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为move(2,A,C,B)，意思是将上面的两个盘子作为整体从A借助C移至B。
  2. 将3号盘从A移至C，一次到位，记为move 3 from A to C。
  3. 处于B上的作为一个整体的两个盘子，再移至C。这一步记为move(2,B,A,C)，意思是将两个盘子作为整体从B借助A移至C。所谓借助是什么意思，等这件事完成了不言自明。
• 从题目的约束条件看，大盘可以随便摞小盘，相反则不允许。在将1号和2号盘作为整体从A移至B的过程中，move(2,A,C,B)实际上是分解为以下3步：
  
  1. move 1 from A to C。
  2. move 2 from A to B。
  3. move 1 from C to B。
• 通过以上步骤，将1号和2号盘作为整体从A移至B，为3号盘从A移至C创造了条件。同样，3号盘一旦到了C，就要考虑如何实现将1号和2号盘当作整体从B移至C的过程了。实际上move(2,B,A,C)也要分解为3步：
  
  1. move 1 from B to A。
  2. move 2 from B to C。
  3. move 1 from A to C。
• 分析move(2,A,C,B)，是说要从两只盘子从A搬至B，但没有C是不行的，因为先要将1号盘从A移到C，给2号盘创造条件从A移至B，然后把1号盘从C移至B。看到这里就能明白借助C的含义了。因此，在构思搬迁过程的参量时，要把3个柱子都用上。
• 定义搬迁函数move(n,A,B,C)，物理意义是将n只盘子从A经B搬到C。考虑上面的分析可以将搬迁过程用图9.14表示。
  
• 图9.14中将move(n,A,B,C)分解为3步。这3步是相关的，相互依存的，而且是有序的，从左至右执行的。
  
  1. move(n-1,A,C,B),理解为将上面的n-1只盘子作为一个整体从A经C移至B。
  2. 输出n : A to C，理解为将n号盘从A移至C，是直接可解结点。
  3. move(n-1,B,A,C)，理解为将上面的n-1只盘子作为一个整体从B经A移至C。这里显然是一种递归定义，当在解move(n-1,A,C,B)时又可想到，将其分解为3步：
     
     1. 将上面的n-2只盘子作为一个整体从A经B到C，即move(n-2,A,B,C)。
     2. 第n-1号盘走从A直接移至B，即n-1 : A to B。
     3. 再将上面的n-2只盘子作为一个整体从C经A移至B，即move(n-2,C,A,B)。

---

下面以3只盘子为例画出递归的与或图，见图9.15。

这个图很像一棵倒置着的树，结点move(3,A,B,C)是树根，与结点是树的分枝，叶子都是直接可解结点。
图9.16和图9.17是为了能够体会调用和返回的过程画出的，目的是为了结合比例加深理解递归过程。

---

递归求解汉诺塔问题

#include <iostream>
using namespace std;

int step = 1;
void move(int, char, char, char);

int main()
{
    int n;//盘输
    cin >> n;
    cout << "在3根柱子上移" << n <<"只盘的步骤为：" << endl;
    move(n,'A', 'B', 'C');
    return 0;
}

//以下函数是被主程序调用的函数
//函数名：move
//输入：m，整形变量，表示盘子数目
//p,q,r为字符型变量，表示柱子标号
//返回值：无
void move(int m, char p, char q, char r)
{
    if(m==1) //如果m为1，则为直接可解结点
    {
        //直接可解结点，输出移盘信息
        cout << "[" << step << "] move 1 # from " << p << " to " << r << endl;
        step++;
    }
    else
    {
        move(m-1, p, r, q); //递归调用move(m-1)
        //直接可解结点，输出移盘信息
        cout << "[" << step << "] move " <<  m << " # from " << p << " to " << r << endl;
        step++;
        move(m-1, q, p, r); //递归调用move(m-1)
    }
}

input：
3
output：
在3根柱子上移3只盘的步骤为：
[1] move 1 # from A to C
[2] move 2 # from A to B
[3] move 1 # from C to B
[4] move 3 # from A to C
[5] move 1 # from B to A
[6] move 2 # from B to C
[7] move 1 # from A to C

---