Day 29 : C语言 - 河内塔的程序递回执行顺序为何？

如标题，这篇想用「图解」去解释河内塔的「程序递回执行顺序」为何
因为当初C有一项作业，叫我们用程序去写出河内塔的执行结果

但我实在是不会写，於是去网路上查，虽然是查到该怎麽撰写了，但它的递回执行顺序实在是很不直觉，单用想的会想破头
最後我是用小画家一个一个画出顺序才想通它，所以想和各位分享一下

首先，要先说说河内塔是什麽
有三个半径不一样的环，「由大到小」依序往上堆叠，你要将A柱子的三个环移动到C柱子，且大环不能叠在小环上

它的初始样子如下图所示:

现在你要用程序将它们的执行次数和顺序依序列印出来，n值代表有几个环:

void example_1(int n, char A, char B, char C) {
	if(n==1) {
		printf("盘子从%c移到%c\n", A, C);
	} else {
		example_1(n-1, A, C, B);
		printf("盘子从%c移到%c\n", A, C);
		example_1(n-1, B, A, C);
	}
}
int main() {
	int n;
	printf("请输入n:");
	scanf("%d", &n);
	example_1(n, 'A', 'B', 'C');
	return 0;
}

结果如下图所示:

它的执行顺序如果画树状图是长这样，「最前面的数字」是n值，「剩下的」分别为example_1这个函数所接收到的char A, Char B, Char C的顺序
「蓝色字」是它会进if还是else，「绿色字」是它的印出顺序和结果

那为什麽顺序2、4、6会分别写在那呢？因为你执行完第一个example_1函数，会跳回「原本的else」继续执行，而下一个执行的是printf，最後才是第二个example_1函数

else {
	example_1(n-1, A, C, B);
	printf("盘子从%c移到%c\n", A, C);
	example_1(n-1, B, A, C);
}

所以它的整体执行顺序如下图所示:

那我们现在来看它「实际移动」的图，看它是如何从柱子A移到柱子C的:

顺序1:

顺序2:

顺序3:

顺序4:

顺序5:

顺序6:

顺序7:
这样就移动成功罗！总共移动的次数为7次

以上就是今天的介绍

希望大家看完能对河内塔的程序递回执行顺序更加了解！

参考资料:
https://lakesd6531.pixnet.net/blog/post/332283123