递归算法：汉诺塔问题

#include <iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

//初始化全局变量s记录步数
int s;

//移动盘子的函数，即打印出移动的过程,参数为函数的编号，盘子的起始位，盘子的终止位
void move(int i, char from, char to) 
{
    printf("第%d步：将第%d个盘子从%c柱移动到%c柱\n", ++s, i, from, to);
}

/*
    递归函数
    1.为了将最下面的盘子移到目标柱上，需要将n-1个盘子移到中间柱上
    2.此时为了将位于中间柱上的最下面的盘子移到目标柱上，需要将n-2个盘子移到起始柱
      上，至于是怎么做到的很复杂，但在这一步之前一定是这样的状态，此时一开始的起始
      柱成为了中间柱
    3.成功将第n-1个盘子移动到目标柱上后，起始柱上有n-2个盘子，中间柱上没有一盘子，
      目标柱上有两个盘子
    4.如此循环往复即可

    传递给函数的参数：
    1）要移动的盘子总数
    2）起始柱（这些盘子现在所处的的位置）
    3）中间柱
    4）目标柱（这些盘子要去到的位置）
*/
void recursion(int n, char start_pos, char middle_pos, char end_pos)
{
    /*
    如果只有一个盘子的话就可以直接移动了,同时也是我们第一轮递归到最后所遇到的状况
    （可以知道，如果要移动的盘子为偶数，那么第一个盘子一定去往中间柱；反之去往终止柱）
    */
    if (n == 1) 
    {
        move(n, start_pos, end_pos);
    }
    else
    {
        /*
        让电脑想办法把开始的n-1个盘子移到中间柱上，也就是说此时的情况变成起始柱上1
        个盘子，中间柱上n-1个盘子
        在进入到这个recursion后，我们的目标又发生了变化，变成了将n-2个盘子从起始
        柱放到终止柱
        如此往复直到满足第一个盘子的移动的条件
        */
        recursion(n - 1, start_pos, end_pos, middle_pos);

        /*
        将n-1个盘子移动到中间柱之后，就可以将第n个盘子移到终止柱上了，注意此时用的
        是第一次调用recursion函数传递的参数，所以就是从start_pos到end_pos
        */
        move(n, start_pos, end_pos);

        /*
        将最下面的盘子移动完后，我们的目标变成将中间柱上的n-1个盘子移动到终止柱上,
        此时起始柱变成中间柱，新的一轮递归开始
        */
        recursion(n - 1, middle_pos, start_pos, end_pos);
    }
}

int main()
{
    int n=0;
    cout << "Please enter how many disk you wanna move, enter 0 to quit this program:"
        "________\b\b\b\b\b\b\b\b";
    
    //scanf()如果读取输入成功，则返回成功匹配和赋值的个数，可以用来判断是否有输入值
    while (scanf_s("%d", &n) == 1 && n)
    {
        s = 0; //全局变量赋值
        recursion(n, ‘a‘, ‘b‘, ‘c‘);
    }

    return 0;
}