河内塔与递归

河内塔，又叫汉诺塔，是法国数学家爱德华·卢卡斯于1883年提出的一个经典数学问题。

给定一个由若干个大小不同的圆盘组成的塔，这些圆盘按照大小递减的方式放在一根柱子上。现在需要把整个塔移动到另外一根柱子上，一次只能移动一个圆盘，并且必须保证较大的圆盘始终位于较小的圆盘下面。

在电影《猩球崛起》中有这样一个片段，凯撒的妈妈 Bright Eyes 在实验室中接受测试时，就表现出了非常优秀的河内塔游戏能力。

河内塔还有一个著名的传说：有64个圆盘组成的塔，上帝命令一群牧师夜以继日地工作，当牧师完成这个任务时，塔就会坍塌，世界也将毁灭。

河内塔问题的解法

我们不妨把这个问题再扩大一下：如果有 n 个圆盘，需要多少次移动才能把塔从一个柱子移动到另外一个柱子？

假设函数 f(x) 表示移动 x 个圆盘所需要的次数，那么移动 n 个圆盘就需要 f(n) 次。

再来考虑最大圆盘的情况。当最大的圆盘被放到另外一个柱子上时，必须保证另外 n-1 个圆盘已经从原来的柱子移动到第三根柱子上，如图：

所以我们可以把这个问题分成三个步骤：

把 n-1 个盘子移动到另外一根柱子上；
把最大的盘子移动到目标柱子上；
再把 n-1 个盘子移动到最大的盘子上面。

其中第一步需要 f(n-1) 次，第二步需要 1 次，第三步又需要 f(n-1) 次。

因此：

f(n) = 2f(n-1) + 1

我们又知道，当只有1个盘子时，只需要移动1次：

f(1) = 1

如果你接触过递归，相信已经可以写出处理这个问题的函数：

def move_count(n):
    if n == 1:
        return 1
    else:
        return 2 * move_count(n - 1) + 1

所以，移动3个盘子需要7次，而移动64个盘子需要：

18446744073709551615

次。

如果一秒钟移动10次，这已经是非常快的速度了，那么移动完64个盘子仍然需要大约 584亿年。太阳系的年龄约为50亿年，未来还能存在多久则取决于恒星演化等因素。

换句话说，64个盘子的河内塔问题所需要的时间远远超出了人类可以想象的尺度。

回到刚刚这5行代码，它到底是怎么解决这个问题的？

假设我们没有学过递归，上学时一定见过类似这样的数学题：

已知：

f(x) = 2f(x-1) + 1
f(1) = 1

求 f(10)。

如果数学不好，可能会这样计算：

f(1) = 1
f(2) = 2 × 1 + 1 = 3
f(3) = 2 × 3 + 1 = 7
……
f(10) = 1023

这种方法计算较小的值还可以，如果计算的值很大，就需要进行大量的重复计算。

从数学上，我们可以这样解决。

已知：

f(1) = 1
f(n) = 2f(n-1) + 1

两边同时加1：

f(n) + 1 = 2(f(n-1) + 1)

令：

U(n) = f(n) + 1

则：

U(n) = 2U(n-1)
U(1) = 2

因此：

U(n) = 2^n

最终得到：

f(n) = 2^n - 1

另外，如果比较善于归纳，也可以直接猜测：

f(n) = 2^n - 1

然后利用数学归纳法进行证明。

递归算法

汉诺塔问题是一个典型的递归问题。递归通常具有这样的特征：一个问题可以拆分成规模更小、形式相同的子问题，同时需要一个明确的边界条件。

例如求自然数的阶乘：

p(1) = 1
p(n) = n × p(n-1)

求 p(10)，在程序中用递归的方式非常容易实现：

#include <stdio.h>

long factorial_recursion(int n){
    if(n == 1){
        return 1;
    }else{
        return n * factorial_recursion(n - 1);
    }
}

int main(int argc, char **argv){
    int N = 10;

    long fac = factorial_recursion(N);

    printf("Factorial is %ld!", fac);

    return 0;
}

编译这个程序之后，可以使用 GDB 对程序运行过程进行分析。

(gdb) b 6
Breakpoint 1 at 0x4013f3: file fac.c, line 6.
(gdb) r
Starting program: C:\Users\cheng\Desktop/a.exe
[New Thread 1032.0x1688]

Breakpoint 1, factorial_recursion (n=10) at fac.c:6
6               return n * factorial_recursion(n-1);
(gdb) n

Breakpoint 1, factorial_recursion (n=9) at fac.c:6
6               return n * factorial_recursion(n-1);
(gdb)

Breakpoint 1, factorial_recursion (n=8) at fac.c:6
6               return n * factorial_recursion(n-1);
(gdb)

Breakpoint 1, factorial_recursion (n=7) at fac.c:6
6               return n * factorial_recursion(n-1);
(gdb)

可以看到，factorial_recursion() 不断调用自己，参数从10逐渐变成9、8、7……

当运行到边界条件之后，函数开始逐层返回。

使用 GDB 的 bt 命令，可以查看当前的调用栈：

(gdb) bt
#0  factorial_recursion (n=2) at fac.c:6
#1  0x00401401 in factorial_recursion (n=3) at fac.c:6
#2  0x00401401 in factorial_recursion (n=4) at fac.c:6
#3  0x00401401 in factorial_recursion (n=5) at fac.c:6
#4  0x00401401 in factorial_recursion (n=6) at fac.c:6
#5  0x00401401 in factorial_recursion (n=7) at fac.c:6
#6  0x00401401 in factorial_recursion (n=8) at fac.c:6
#7  0x00401401 in factorial_recursion (n=9) at fac.c:6
#8  0x00401401 in factorial_recursion (n=10) at fac.c:6
#9  0x00401429 in main (argc=1, argv=0x372a00) at fac.c:11

上面的 #0 到 #9 可以理解为当前调用栈中的栈帧。每个栈帧保存着当前函数运行所需要的信息，包括局部变量和返回地址等。

可以看到，整个递归调用实际上就是函数不断入栈、再不断出栈的过程。当程序调用一个新的函数时，会创建对应的栈帧；当函数执行完成后，对应的栈帧就会被销毁，程序返回上一层调用。

河内塔的移动步骤

我们把河内塔的问题再深入一些，要求程序不仅计算移动次数，还要打印出具体的移动步骤：

#include <stdio.h>

void move_tower(int n, char a, char b, char c){
    if(n > 0){
        move_tower(n - 1, a, c, b);

        printf("Move %d  %c -> %c\n", n, a, b);

        move_tower(n - 1, c, b, a);
    }
}

int main(int argc, char **argv){
    char pa = 'a';
    char pb = 'b';
    char pc = 'c';

    move_tower(3, pa, pb, pc);

    return 0;
}

这里的 move_tower() 正好体现了前面介绍的递归思想：先处理 n-1 个盘子，再移动当前最大的盘子，最后再处理剩下的 n-1 个盘子。

从河内塔可以很直观地看到，递归并不是某种特殊的语法技巧，而是一种将复杂问题不断分解成规模更小、结构相同的问题的方法。

同时，通过 GDB 查看调用栈，又可以看到递归在程序运行过程中是如何通过栈帧实现的。