# Tower of Hanoi

汉诺塔是递归和分治的经典问题，而同学们也曾经在理解这个程序的时候遇到困难。遇到困难是正常的：C/C++ 中的 “函数” 和数学的函数很不一样，例如我们可以把 Fibonacci 数列的递归写成

```c++
int x = f(n - 1);
int y = f(n - 2);
// 也可以 return y + x;
return x + y;
```

或是任意调换函数调用的次序，但汉诺塔不行。

不行的根本原因在于汉诺塔中的 printf 会带来全局的副作用。但 C/C++ 遵循 “顺序执行” 的原则，函数的执行有 “先后” (不像数学的函数，先后是无关的)，按照不同顺序调用会导致程序输出不同的结果。实际上，C 标准中 `return f(n - 1) + f(n - 2);` 甚至不保证从左到右的调用顺序。(但现代编译器为了防止产生难以理解的执行，通常按照自然顺序调用、不做激进优化。)

在 AI 时代，“理解程序” 也发生了非常显著的变化。下面的可视化脚本可以让你看到汉诺塔的执行过程：

```gdb
set pagination off
source hanoi_viz.py
hanoi-viz on
run
```