递归就是递归就是递归就是递归

递归

递归在编程里是一个很常见的思想。

汉诺塔——递归经典习题

汉诺塔基本思想
假定A柱上有n个要移动的圆盘，每次只能移动一个圆盘，圆盘必须按照从小到大的顺序叠放
目标是将所有A柱上的圆盘移动到C柱，那肯定要把最下面的圆盘移动到C，再把其他圆盘移动上去
n要从A移动到C，n-1就要移动到B，再从B移动到C。这就是说每移动1次n,都要移动2次n-1
故写了一个Hanoi需调用2个Hanoi
定义的形式参数中，x为出发柱，y为不干扰柱，z为目标柱
三个数轮流替换
前一个Hanoi的意思：要把x上的n号圆盘移动到z，就要把x上的n-1号圆盘移动到y
后一个Hanoi的意思：要把y上的n-1号圆盘移动到z，就要把y上的(n-1)-1号圆盘移动到x

#include<stdio.h>

void Hanoi(int n,char x,char y,char z){
    if(n == 1){
        printf("%d:%c-->%c\n",n,x,z);
    }else{
        Hanoi(n-1,x,z,y);           //n-1从原来的柱子移动到不干扰n移动的柱子上
        printf("%d:%c-->%c\n",n,x,z);
        Hanoi(n-1,y,x,z);           //n-1从不干扰n移动的柱子移动到n到达的柱子上
    }
}

//2023.4.5尝试重写
void Hanoi1(int n,char a,char b,char c){
    if(n == 1){
        printf("%d from %c to %c\n",n,a,c);
    }else{
        Hanoi1(n-1,a,c,b);
        printf("%d from %c to %c\n",n,a,c);
        Hanoi1(n-1,b,a,c);
    }
}
//以3个圆盘的汉诺塔为例
//要把3号圆盘移到C，就需要把2号圆盘移到B，就需要把1号圆盘移到C
//此时不断在前一个Hanoi中调用，直到调用到最上面的1号圆盘
//1号圆盘为最上面的圆盘，故最先移动（在程序中体现为输出）
//接下来要做的是将2号圆盘从B移动到C，那么就需要1号圆盘移动到A
//此时调用的是后一个Hanoi，也会一直调用到n = 1
//最后再把1号圆盘移动到C
int main(){
    Hanoi(4,'A','B','C');
    Hanoi1(3,'X','Y','Z');
    return 0;
}