递归处理Hanoi塔问题分析

一、综述
程序设计中基本控制结构有三种：顺序、分支与循环。Corrado Böhm 和 Guiseppe Jacopini 在Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules [1]中证明结构定理（任何逻辑问题均可仅用顺序、选择 [IF THEN ELSE] 和循环 [DO WHILE] 结构来解决）。

顺序结构：基本算术、逻辑和位运算，数据移动与复制，寄存器与处理器控制操作。有些将子例程和函数归入顺序结构，有些却将其视为特殊分支结构。

分支结构：直接和间接跳转（包括臭名昭著的 GOTO）、条件跳转 (IF)、嵌套 IF和CASE (SWITCH) 结构。

循环结构：基本的 DO 循环、DO WHILE 和 DO UNTIL、FOR循环。

顺序结构是构造基本递归函数的复合计算应用；分支结构是部分递归运算中的极小化运算应用；循环结构是原始递归运算应用；

本文通过递归应用在程序设计中的实现来讨论这三种基本控制结构。Hanoi塔问题是个比较典型的递归应用问题，其问题的求解需依赖函数递归调用来处理，所以本文重点讨论递归应用中的Hanoi塔问题，即在Hanoi塔问题中应用递归时如何占用大量计算机系统资源（包括堆栈、软中断和存贮空间等）和消耗大量处理时间，并进一步探讨在计算机软件理论上是否存在递归问题并行处理的可能性。

二、递归处理 Hanoi 塔问题
1、递归定义和递归论
定义对象类的方法称为递归定义。递归定义的陈述：存在一定原始对象在被定义的类中，我们给出一些方法，运用这些方法，应给定某些已存在类的某些对象，可以产生该类中的新对象，被定义类中的全体成员恰好而且仅仅是由原始对象反复使用获取，这种对象类的方法称为递归定义。这是递归论中一般意义上的递归定义。递归论亦称能行性论，主要讨论能行计算、能行判定问题。

可计算函数是一般递归函数（Church, 1936），可计算函数是可用 Turing 机计算的函数（Turing, 1936），一般递归函数是可用 Turing 机计算的函数 (Kleene)，这便是 Church-Turing 论点，借此可判定某些问题是可以能行地解决（判定）的。“能行地解决”表示“有一般递归函数”，而“能行地判定”表示“有/没有相应的一般递函数”。

函数 f 的可计算性是指，当自变元 x 给出后，若 f (x) 有定义则可在有限步骤内得出该函数的值；此外，当 f (x) 无定义时，若能在有限步内判知，则称 f 是可完全计算的，否则称之为半计算的。

2、递归应用中的Hanoi塔问题
根据上述概念，讨论能行性时必须注意是否可以计算（亦即可在有限步骤内计算），但实际上进行计算时要求计算简单，需要考虑时间与空间复杂度。计算复杂度通常根据计算机计算该函数时所用的存储单元数（空间复杂度）以及所需的计算步数（时间复杂度）进行分析，一般按照 Turing 机加以计算分析。

Hanoi塔问题是一个典型的可用递归方法解决的问题（递归问题通常可转化为非递归问题）[2]。算法分析如下，设A上有n个盘子。

如果n=1，则将圆盘从A直接移动到C。

如果n=2，则：

（1）将A上的n-1（等于1）个圆盘移到B上；

（2）再将A上的一个圆盘移到C上；

（3）最后将B上的n-1（等于1）个圆盘移到C上。

如果n=3，则：

A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：

（1）将A上的n`-1（等于1）个圆盘移到C上。

（2）将A上的一个圆盘移到B。

（3）将C上的n`-1（等于1）个圆盘移到B。

B）将A上的一个圆盘移到C。

C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：

（1）将B上的n`-1（等于1）个圆盘移到A。

（2）将B上的一个盘子移到C。

（3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。

从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。 显然这是一个递归过程，程序如下：（开发工具 Turbo C 2.0、计算环境 MS-DOS）

程序 hanoi.c

#include "time.h"

move( int n, int x, int y, int z )

{

    if( n==1 )

        printf( "%c-->%c ", x, z );

    else

    {

        move( n-1, x, z, y);

        printf( "%c-->%c ", x, z );

        move( n-1, y, x, z );

    }

}

main()

{

    int h;

    long timstart = 0;

    long timend = 0;

    printf( " input number: " );

    scanf( "%d",&h );

    printf( "the step to moving %2d diskes: ", h );

    time( &timstart );

    move( h, ’a’, ’b’, ’c’ );

    time( &timend );

    timend -= timstart;

    printf( " the process time is %ld seconds ", timend );

}　　

从程序中可以看出move函数是一个递归函数，其功能是把x上的n个圆盘移动到z 上。当n==1时，直接把x上的圆盘移至z上，输出xàz。如n!=1则分为三步：递归调用move函数，把n-1个圆盘从x移到y；输出xàz；递归调用move函数，把n-1个圆盘从y移到z。在递归调用过程中n=n-1，故n的值逐次递减，最后n=1时，终止递归，逐层返回。当n=3 时程序运行的结果如下：

aàc

aàb

càb

aàc

bàa

bàc

aàc

3、递归应用中的Hanoi塔问题分析
1）Hanoi塔问题中函数调用时系统所做工作

一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：

①将所有的实参、返回地址等信息传递给被调用函数保存。

②为被调用函数的局部变量分配存储区；

③将控制转移到被调用函数的入口。

从被调用函数返回调用函数前，系统也应完成3件事：

①保存被调用函数的结果；

②释放被调用函数的数据区；

③依照被调用函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。

一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i＋1层。反之，退出第i层递归应返回至上一层，即i－1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。

2）Hanoi塔问题递归程序的复杂度分析

① 运行hanoi程序的时间

程序 hanoi.c 在硬件环境为赛扬 400MHz、内存128M的计算平台（不同机器运行时间有一定差别）运行，可得出如下时间结果：

盘子数       时间结果

<=12个        <=1秒

14个          2秒

16个         13秒

20个        204秒

② 时间复杂度

程序所花时间正比于所输出的信息行数目，而信息行的数目则等价于盘子的移动次数。考察程序，设盘子移动次数为moves（n），则：

moves(n)=    
       用迭代方法计算公式，得到结果moves(n)=2n-1。因此，hanoi函数的时间复杂度为O(2 n) 。

③ 空间复杂度

       从每个塔上移走盘子时是按照LIFO进行，因此可以把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是n个。如果使用链表形式的堆栈，只需申请n个元素所需要的空间。如果使用的是基于公式化描述的堆栈，塔1和塔2的容量都必须是n，而塔3的容量是n－1，因此所需要的空间总数为3n－1。

Hanoi塔问题的复杂性是以n为指数的函数，因此在可以接受的范围内，只能解决n值比较小（n<=30）的hanoi问题。对于这个较小的n值，堆栈在空间需求上的差别相当小，可以随意使用。

三、结论
通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论：

1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；

2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但

3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。

参考文献：

[1] Corrado Böhm, Guiseppe Jacopini [1966]. “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules”, Communications of the ACM, No. 5, May 1966, pp 366-371

[2] Donald E. Knuth [1998]. The Art of Computer Programming. Addison-Wesly

[3] Hockney R. W., C. R. Jesshope [1988]. Parallel Computers-2, Architecture, Programming and Algorithms. Adam Hilger Ltd., Bristol, England.

[4] John L. Hennessy, David A. Patterson [2002]. Computer Architecture: A Quantitative Approach. Elsevier Science Pte Ltd.

[5] Kenneth C. Louden [1997]. Compiler Construction Principles and Practice. PWS Publishing Company

[6] Sara Baase, Allen Van Gelder [1999]. Computer Algorithms: An Introduction to Design and Analysis, Addison-Wesley.

[7] Wilf, H.S. [1986]. Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, N.J.