算法―用栈实现递归

递归，很多语言都支持递归，它的本质就是利用栈去实现的。这里讨论用栈去实现递归，就是为了更深刻的理解递归的本质，同时也更深的理解了栈等数据结构的用法。
 
下面看一下自然数加和问题。
 
f(n) = 1+2+...+n
 
用递归的方法如下：
 
    public int triangle( int n)
    {
        if ( 1 == n )
        {
            return 1;
        } else
        {
            return n + triangle(n-1);
        }
    }
 

如果用栈去实现这个递归，该如何实现呢？

看下面的代码：

先构造一基本的数据结构：Params，它包含两个成员变量 n(问题中的n)和returnAddress(返回地址，相当于函数调用过程中编译器为我们做的返回地址)

Params.java

package zieckey.datastructure.study.recursion;

public class Params // parameters to save on stack

{
    private int    n;
    private int    returnAddress;

    public Params( int nn, int ra )
    {
        setN( nn );
        setReturnAddress( ra );
    }

    public void setReturnAddress( int returnAddress )
    {
        this.returnAddress = returnAddress;
    }

    public int getReturnAddress()
    {
        return returnAddress;
    }

    public void setN( int n )
    {
        this.n = n;
    }

    public int getN()
    {
        return n;
    }
} // end class Params


 

现在再来构建一个栈，用于保存模仿递归过程中回调的数据：

StackParams.java

package zieckey.datastructure.study.stack;

import zieckey.datastructure.study.recursion.*;
/**
 * Demonstrates stacks
 *
 * @author
 */
public class StackParams
{
    private int            maxSize;    // size of stack array

    private Params[]    stackArray;
    private int            top;        // top of stack


    public StackParams( int maxSize )
    {
        this.maxSize = maxSize;// 设置数组大小

        stackArray = new Params[maxSize];// 创建数组

        top = -1;// 还没有任何元素

    }

    public void push( Params j )
    {// 入栈

        if ( isFull( ) )
        {
            System.out.println( "Cannot insert item " + j + "! The stack is full." );
        } else
        {
            top++ ;
            stackArray[top] = j;
        }
    }

    public Params pop()
    {// 出栈

        if ( isEmpty( ) )
        {
            System.out.println( "The stack is empty." );
            return null;
        } else
        {
            Params pa = stackArray[top];
            stackArray[top] = null;//清空

            top-- ;
            return pa;
        }
    }

    public Params peek()
    {// 返回栈顶元素

        return stackArray[top];
    }

    public boolean isEmpty()
    {
        return ( -1 == top );
    }

    public boolean isFull()
    {
        return ( maxSize - 1 == top );
    }

}

 

好了，基本的工具都准备好了，下面就是如何实现通过栈来模拟递归算法的过程：

StackTriangleApp.java

 

package zieckey.datastructure.study.recursion;

// stackTriangle.java

// evaluates triangular numbers, stack replaces recursion

// to run this program: C>java StackTriangleApp

import java.io.*; // for I/O


import zieckey.datastructure.study.stack.StackParams;

// //////////////////////////////////////////////////////////////

class StackTriangleApp
{
    static int            theNumber;
    static int            theAnswer;
    static int            codePart;
    static Params        theseParams;
    static StackParams    theStack;

    public static void main( String[] args ) throws IOException
    {
        System.out.print( "Enter a number: " );
        System.out.flush();
        theNumber = getInt();
        recTriangle( theNumber );
        System.out.println( "Triangle=" + theAnswer );
    } // end main()


    // -------------------------------------------------------------

    public static void recTriangle()
    {
        theStack = new StackParams( 50 );
        codePart = 1;
        while ( step() == false ) // call step() until it's true

        {
            ;
        }
    }

    // -------------------------------------------------------------

    public static void recTriangle( int size )
    {
        theStack = new StackParams( size );
        codePart = 1;
        while ( step() == false ) // call step() until it's true

        {
            ;
        }
    }

    // -------------------------------------------------------------

    public static boolean step()
    {
        switch ( codePart )
        {
            case 1 : // initial call

                theseParams = new Params( theNumber, 6 );//returnAddress=6，结束时用

                theStack.push( theseParams );
                codePart = 2;
                break;
            case 2 : // method entry，每次入栈后，判断是否n=1，不等于1就继续入栈操作，等于1就返回，开始做计算

                theseParams = theStack.peek();
                if ( theseParams.getN() == 1 ) // test

                {
                    theAnswer = 1;
                    codePart = 5; // exit

                } else
                    codePart = 3; // recursive call

                break;
            case 3 : // method call

                /**
                 * Params.returnAddress=4
                 */                
                Params newParams = new Params( theseParams.getN() - 1, 4 );
                theStack.push( newParams );
                codePart = 2; // go enter method，每次入栈后，就返回到主处理流程 case 2，判断。

                break;
            case 4 : // calculation

                theseParams = theStack.peek();
                theAnswer = theAnswer + theseParams.getN();
                codePart = 5;
                break;
            case 5 : // method exit

                theseParams = theStack.peek();
                codePart = theseParams.getReturnAddress(); // (4 or 6)

                theStack.pop();
                break;
            case 6 : // return point

                return true;
        } // end switch

        return false; // all but 7

    } // end triangle


    // -------------------------------------------------------------


    public static String getString() throws IOException
    {
        InputStreamReader isr = new InputStreamReader( System.in );
        BufferedReader br = new BufferedReader( isr );
        String s = br.readLine();
        return s;
    }

    // -------------------------------------------------------------

    public static int getInt() throws IOException
    {
        String s = getString();
        return Integer.parseInt( s );
    }
    // -------------------------------------------------------------

} // end class StackTriangleApp


 

程序中的returnAddress有点难以理解，这个只是表面上看起来难，其实不难，把程序跟踪调试下就知道是怎么回事了，而且更能观察到栈的变化，同时就知道了递归实现的本质。