C语言编程--递归程序--Hanoi塔

任务：
We have $3$ pegs and $N$ disks that fit onto the pegs. The disks differ in size, and are initially arranged on one of the pegs, in order from largest (disk $N$) at the bottom to smallest (disk $1$) at the top.
The task is to move the stack of disks to the right one position (peg), while obeying the following rules:

• only one disk may be shifted at a time, and
• no disk may be placed on top of a smaller one.

实现：

#include <stdio.h>void hanoi(int N, int d);
void shift(int N, int d);int main(){// 测试3个盘子printf("Testing 3 pegs start...\n");hanoi(3,1);printf("Testing 3 pegs end....\n");//测试5个盘子printf("Testing 5 pegs start...\n");hanoi(5,1);printf("Testing 5 pegs end...\n");return 0;
}void hanoi(int N, int d){if (N == 0) {return ;}//先把N-1个盘子向左移动hanoi(N-1, -d);//再把第N个盘子向右移动shift(N, d);//最后把N-1个盘子向左移动到第N个盘子上hanoi(N-1, -d);
}void shift(int N, int d){if (d > 0) {printf("shift(%d, +%d)\n", N,d);}else {printf("shift(%d, %d)\n", N,d);}}

递归调用图

递归调用树

• 对应图5.7左下侧的hanoi(3,+1)的递归调用图
• 采用后续遍历的方式即可得到hanoi(3,+1)的递归调用返回序列