从汉诺塔问题看函数尾部递归的消除（C语言版）

本文主要是介绍从汉诺塔问题看函数尾部递归的消除（C语言版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/************************************************************************************************
汉诺塔函数尾部递归的消除

由于函数调用是通过堆栈来完成，因此函数的递归将会造成大量内存空间的浪
费，因此在没有必要的情况下不宜用递归。有时我们可以用递归的思想来考虑问题，
然后通过某些方法来消除递归，而这里仅仅考虑当递归语句是函数中最后执行的语
句情况下的消除方法，即通过使用循环可以将递归改变为迭代。下面第一个程序是

常见的汉诺塔程序，第二个程序是递归消除的实现，程序质量大幅度提升。

程序在TC-WIN成功编译运行

Leo,2006/10/6
stefzeus@163.com

************************************************************************************************/

/* Answer for Hanoi */
/* move() uses two recursion to solve the problem. */

#include <stdio.h>
#include <conio.h>
#include <dos.h>

void move(int ,int ,int ,int );

void main()
{
    int disk;
    clrscr();
    while(1)
       {
        printf("How many disk do you move:");
        scanf("%d",&disk);
        putchar('/n');
        if( disk<21 && disk >0 )
            break;
        else
            printf("Warring:The disks are too more or too less,"
                    "please input again./n");

       }
    move(disk,1,3,2);
    getch();

}

/* move:moves count disk from start to finish using
temp for temporary storage. uses two recursion */
void move(int disk,int start,int finish,int temp)
{

    if(disk>0)
       {
        move(disk-1,start,temp,finish);        /* firth recursion */
        printf("move %dth from %d to %d./n/n",disk,start,finish);
/*        sleep(1);      */           /* delay make user can see the result */
        move(disk-1,temp,finish,start);       /* second recursion */
       }

}

/****************************************************************************************************************/

/*                  Hanio Of Second Edition                               */
/*      move() uses noly one recursion (get rid of recursion in the tail */
/* of function. )                                                        */

#include <stdio.h>
#include <conio.h>
#include <dos.h>

void move(int ,int ,int ,int );

void main()
{
    int disk;
    clrscr();
    while(1)
       {
        printf("How many disk do you move:");
        scanf("%d",&disk);
        putchar('/n');
        if( disk<21 && disk >0 )
            break;
        else
            {
            printf("Warring:The disks are too more or too less,"
                    "please input again./n");
            continue;
            }
       }
    move(disk,1,3,2);
    getch();

}

/* move:moves count disk from start to finish using
        temp for temporary storage. uses one recursion.      */
void move(int disk,int start,int finish,int temp)
{
    int t;
    while(disk>0)
        {
        move(disk-1,start,temp,finish);        /* firth recursion */
        printf("move %dth from %d to %d./n/n",disk,start,finish);
        sleep(1);                 /* delay make user can see the result */
        disk--;
        t=start;
        start=temp;
        temp=t;
        }

}