By zieckey ()
递归，很多语言都支持递归，它的本质就是利用栈去实现的。这里讨论用栈去实现递归，就是为了更深刻的理解递归的本质，同时也更深的理解了栈等数据结构的用法。
下面看一下自然数加和问题。
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有点难以理解，这个只是表面上看起来难，其实不难，把程序跟踪调试下就知道是怎么回事了，而且更能观察到栈的变化，同时就知道了递归实现的本质。
阅读(9267) | 评论(0) | 转发(0) |
