数据结构复习篇:用栈实现递归

66 阅读 0 评论 44 点赞

我是靠谱客的博主爱笑故事，最近开发中收集的这篇文章主要介绍数据结构复习篇:用栈实现递归，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

也许大家会疑问：复习完栈应该到队列了吧。我开始也是这样想的，但用栈实现递归，是一个难点。说实话，我以前学习的时候，就在这一处卡住了，当时我烦躁了好几天，但可能由于突然被什么东西转移了注意力，所以就这样跳过去了。不知道用栈实现递归，也确实不大影响后面的学习，但我可以肯定，如果你觉得世界上有一些东西难以理解而不愿面对，那自信将会由此削弱。当然，遇到困难可以适当地把它放下，但逃避应该是暂时的，必须鼓励自己――－也许是几天，也许是几个月――但绝对要攻克它！

很兴奋，经过刚才的思考：我先是在草稿纸上进行了一些“画画”的工作，当我把用栈实现汉诺塔的搬运过程，一步步地的画在纸上的时候，思维由这些具体的步骤而变得清晰起来（“画画”确实是一种有助于思考的方法。很可惜我没有扫描工具，否则我可以把这些画插在我这篇文章中，将会非常生动）。然后我想到一个不错的比喻来帮助自己理解这一个过程。这一个比喻，我非常得意，一会与大家分享。现在，我自认为把这个问题完全攻克了（请大家原谅我的自恋^_^），所以才迫不及待地要把思考的结果写下来。

我还是按书上那个汉诺塔的例子来表述这个思想，而且把汉诺塔的递归用栈实现，也恰好有一定的难度。但我建议，大家看完我这篇文后，不妨试着一个递归用栈去实现一下，很容易就检验出你是否真的领会了其中的思想。

－、汉诺塔问题：

有三根柱子分别叫A柱、B柱、C柱。现假设有N个圆盘（都是按从大到小依次放入柱中的）已经放在了A柱上，我们的任务就是把这N个圆盘移动到C柱。但移动的过程，必须遵守大盘永远在小盘的下面这一个原则。

二、移动汉诺塔的递归思想：

1、先把A柱上面的(N-1)个圆盘移到B柱（这一步使问题的规模减少了1）。

2、再把A柱上剩下的那个最大的圆盘移到C柱。

3、最后把B柱上的（N-1）圆盘移到C柱。

当我们写递归函数的时候，我们先假设我们即将写的这个函数已经能解决n个圆盘的汉诺塔问题了，递归就是这样一种思想：它告诉我们程序员，做梦也是一件有意义的事^_^。那么我们现在假设这个函数的接口是这样的：

Void TOH(int n, Pole start, Pole goal, Pole temp )（第一次调用时，我们是这样用这个函数的：

Void TOH(N, A, C, B);N是圆盘数、A是起始柱、B是暂时柱、C是目标柱。）然后，我就利用上面分析的递归步骤（当然，递归中的初始情况base case也是不能忘记的），在该函数体里面，继续调用该函数，便得到了递归函数：

void TOH( int n, Pole start, Pole goal, Pole temp) // 把n个圆盘从start柱移到goal柱，temp柱作为辅助柱
{
     if (n == 0 ) return ;     // base case
    TOH(n - 1 , start, temp, goal);     // 把n-1个圆盘从start柱移到temp柱，goal作为此次的辅助柱
    move(start,goal);         // 从start柱移动一块圆盘到goal柱
    TOH(n - 1 , temp, goal, start);     // 把temp柱中的n-1个圆盘移到goal柱
     return ;
}

三、用栈实现递归的思想：

现在，我将用一个自认为得意的比喻，来表达这个思想。我们不妨设想有这样一个环境：有一家独特的公司，这家公司的上司是这样给他们的下属分配任务的：当有一个任务来临的时候，一位上司就会把这个任务写在一张格式统一的纸上（这张纸象征着栈中的一个元素，但纸上的内容与栈中元素的内容会有一些差异），这张纸上一般会记录下面这两个信息：

这位上司A会把这张 任务纸放到公司里一张专门的办公桌上（它是栈的象征）。

好了，现假设，上司A把这张任务纸放在了那张专门的办公桌上，一个下属B查看办公桌时，发现了这个任务。他并没有立刻就去执行这个任务，因为他们公司有一个奇怪但令人鼓舞的规定：

1、 如果你可以把一个任务分解成更小的几个子任务，你便可以把这些分解后的子任务，留给别人去做。

2、当你把任务分解后，你必须把这些子任务，分别写在任务纸上，并按照这些子任务的执行顺序，从后到先，依次叠放在那张办公桌上，即保证最上面的那张纸，就是应该最先执行的任务。

那么下属B发现，他可以把上司A写在那张纸上的任务分解成三个子任务：

然后，B把这三张纸依次从上到下地叠放在办公桌上，那么他可以下班了^_^。

之后，下属C来上班，发现了办公桌上叠放了三张纸，注意，公司有如下规定：

通常（因为还有一种特别情况，将下面给出），每个员工只需负责办公桌上，放在最上面的那张纸上的任务。

C拿起最上面那张纸，就是B写的执行顺序为1的那张纸，他立刻笑了。他也模仿B，把这个任务分解成：

1、这里有N－2个圆盘，把这些圆盘从A柱移到C柱。

2、这里有1个圆盘，把这个圆盘从A柱移到B柱。

3、这里有N－2个圆盘，把这些圆盘从C柱移到B柱。

然后，他把三个子任务的三张任务纸替换掉B写的那张纸。那么他又可以下班了。

就这样，员工们很轻松的工作。直到有一个员工，假设他名叫X，比较不幸，他发现办公桌上最上面的那张纸上写着：把一个圆盘从某根柱移到另一根柱。因为这个任务根本就没办再分了，所以可怜的X就只好亲自动手去完成这个任务，但事情并没有结束，因为该公司规定：

如果你无法再分解这个任务，你就要亲自完成这个任务，并且如果办公桌上还有任务纸，那你必须继续处理下一张任务纸。

正如前面所说，办公桌上的纸的处理方式，就是栈的后进先出的方式，而任务纸就是栈的元素。这应该很容易理解。难点在于两点：

1、栈元素的内部结构如何定义？我们可以把栈元素看作一个结构体，或者看作一个类对象，而任务的规模应该是类对象的一个整形数据成员，但任务描述，就不太好处理了。事实上，我们可以对任务进行分类，然后只要用一个枚举类型或是其他数据类型，来区分这个任务属于哪种分类。

2、如何把上面所分析的过程，用程序表达出来？好了，如果你耐心的阅读了上面的文字，那么理解下面这个程序，应该非常容易了：

我对书中的程序稍作改写，也作更丰富的注释，读程序的时候，注意联系我上文所作的比喻：

#include < iostream >
#include < conio.h >
#include " StackInterface.h " // 这个头文件，可以在栈那篇文章中找到，也可以自己用标准库中的stack改一下面的程序即可
using namespace std;
/*
现在我们来定义一个栈的元素类：TaskPaper任务纸
由下属B、C对子任务的分解情况，很容易看出，
可以把任务分成两类：
1、移动n-1个圆盘。这说明，这种任务可以继续分解。
2、移动1个圆盘。这说明，这种任务无法再分，可以执行移动操作。
那么，我们可以定义一个枚举类型，这个枚举类型作为栈元素
的一个数据成员，用来指示到底是继续分解，还是作出移动操作。
*/
enum Flag {toMove, toDecompose}; // 移动、继续分解
enum Pole {start, goal, temp};     // 柱的三种状态，既然起始柱、目标柱、临时柱（也叫辅助柱）

class TaskPaper     // 任务纸类，将作为栈的元素类
{
public :
    Flag flg;     // 任务分类
     int num;         // 任务规模
    Pole A, B, C;     // 三根柱

    TaskPaper( int n, Pole a, Pole b, Pole c, Flag f)
    {
        flg = f;
        num = n;
        A = a;
        B = b;
        C = c;
    }
};

void TOH( int n, Pole s, Pole t, Pole g) // 用栈实现的汉诺塔函数
{
    LStack < TaskPaper *> stk;
    stk.push( new TaskPaper(n,s,t,g, toDecompose));     // 上司A放第一张任务纸到办公桌上

    TaskPaper * paperPtr;
     long step = 0 ;
     while (stk.pop(paperPtr))     // 如果办公桌上有任务纸,就拿最上面的一张来看看
    {
         if (paperPtr -> flg == toMove || paperPtr -> num == 1 )
        {
             ++ step;
             if (paperPtr -> A == start && paperPtr -> B == goal)
            {
                cout << " 第 " << step << " 步：从A柱移动一个圆盘到B柱。 " << endl;
            }
             else if (paperPtr -> A == start && paperPtr -> C == goal)
            {
                cout << " 第 " << step << " 步：从A柱移动一个圆盘到C柱。 " << endl;
            }
             else if (paperPtr -> B == start && paperPtr -> A == goal)
            {
                cout << " 第 " << step << " 步：从B柱移动一个圆盘到A柱。 " << endl;
            }
             else if (paperPtr -> B == start && paperPtr -> C == goal)
            {
                cout << " 第 " << step << " 步：从B柱移动一个圆盘到C柱。 " << endl;
            }
             else if (paperPtr -> C == start && paperPtr -> A == goal)
            {
                cout << " 第 " << step << " 步：从C柱移动一个圆盘到A柱。 " << endl;
            }
             else if (paperPtr -> C == start && paperPtr -> B == goal)
            {
                cout << " 第 " << step << " 步：从C柱移动一个圆盘到B柱。 " << endl;
            }
        }
         else
        {
             int num = paperPtr -> num;
            Pole a = paperPtr -> A;
            Pole b = paperPtr -> B;
            Pole c = paperPtr -> C;

             if (a == start && c == goal)
            {
                 // 书中仅写了这一种情况，而后面的五种的情况被作者大意地认为是相同的，
                 // 于是程序出错了。我估计没有几个人发现这个问题，因为只我这种疑心很重的人，
                 // 才会按照书中的思路写一遍这种程序^_^
                stk.push( new TaskPaper(num - 1 , b, a, c, toDecompose)); // 子任务执行顺序为3
                stk.push( new TaskPaper( 1 ,a,b,c,::toMove));     // 子任务中执行顺序为2
                stk.push( new TaskPaper(num - 1 , a, c, b, toDecompose)); // 子任务中执行顺序为1
            }
             else if (a == start && b == goal)
            {
                stk.push( new TaskPaper(num - 1 , c, b, a, toDecompose)); // 为goal的柱状态不变,其它两根柱的状态互换
                stk.push( new TaskPaper( 1 ,a,b,c,::toMove));     // 移动操作中,柱的状态不变
                stk.push( new TaskPaper(num - 1 , a, c, b, toDecompose)); // 为start的柱状态不变,其它两根柱的状态互换
            }
             else if (b == start && a == goal)
            {
                stk.push( new TaskPaper(num - 1 , a, c, b, toDecompose));
                stk.push( new TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new TaskPaper(num - 1 , c, b, a, toDecompose));
            }
             else if (b == start && c == goal)
            {

                stk.push( new TaskPaper(num - 1 , b, a, c, toDecompose));
                stk.push( new TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new TaskPaper(num - 1 , c, b, a, toDecompose));
            }
             else if (c == start && a == goal)
            {

                stk.push( new TaskPaper(num - 1 , a, c, b, toDecompose));
                stk.push( new TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new TaskPaper(num - 1 , b, a, c, toDecompose));
            }
             else if (c == start && b == goal)
            {

                stk.push( new TaskPaper(num - 1 , c, b, a, toDecompose));
                stk.push( new TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new TaskPaper(num - 1 , b, a, c, toDecompose));
            }

        }

        delete paperPtr;

    }
}

void main()
{

    TOH( 3 ,start,temp,goal);
    getch();

}

总结下一下用栈实现递归的算法
1、进栈初始化：把一张TaskPaper放到办公桌面上。
2、出栈，即从办公桌上取一张TaskPaper，如办公桌上没有任务纸（出栈失败），则到第4步。
3、取出任务纸后，根据任务的信息，分两种情况进行处理：
A、如果任务不可再分，则执行这个任务（在上面这个程序中，体现为把搬运动作打印出来），返回到第2步。
B、否则，划分成若干个子任务，并把这些子任务，按照执行任务的相反顺序放进栈中，保证栈顶的任务永远是下一次出栈时最应优先处理的，返回到第2步。
4、其它处理。

补充：刚才（现在是10月3号）我试着用我上文的思想，用栈实现Fibonacci（斐波那契）数列的递归，真的很有用，思路非常清晰。我把这段程序发到这里来，相信通过上面的汉诺塔程序和这个斐波那契程序，可以更好的帮助大家理解上文的思想(由于昨晚电脑崩溃，用ghost重装了系统，发现我前几天写的程序全丢失了，下面这个程序中用到的栈，是标准库中的stack)：

/*
这是我个人的头文件，用来定义各种函数
文件名：zyk.h
*/
#ifndef ZYK_H
#define ZYK_H
#include < iostream >
#include < stack >
using namespace std;

namespace zyk
{
     // Fibonacci数列的递归函数
     long fibr ( int n);

     // 用栈实现fibr递归
     long fibr_stack( int n);
}

long zyk::fibr( int n)
{
     if (n == 1 || n == 2 )
    { return 1 ;}

     return fibr(n - 1 ) + fibr(n - 2 );
}

long zyk::fibr_stack( int n)
{
     long val = 0 ;
    stack < int > stk;
    stk.push(n);       // 初始化栈

     while ( ! stk.empty())     // 如果办公桌上不是空的，即有任务纸
    {
         int nn = stk.top();     // 查看这张纸
        stk.pop();             // 拿开这张纸

         if (nn == 1 || nn == 2 )
        {
            val += 1 ;         // 累加。
        }
         else
        {
            stk.push(nn - 1 );     // 分成两个子任务
            stk.push(nn - 2 );     // 对于这两个子任务，其先后执行顺序是无关紧要的。
        }

    }

     return val;
}

#endif