当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

递归------消除递归(递归原理解析)

发表于: 2010-08-20   作者:12616383   来源:转载   浏览:
摘要: 递归原理:大部分编译器都是使用栈来实现递归的,当调用一个方法的时候编译器会将参数和返回地址压入栈中,然后把控制转移给这个方法,当方法返回时,这些值退栈,参数小时。   下面是模拟的递归的过程: package digui; public class XiaoDigui{ static int theNumber; static int theAnswer; sta

递归原理大部分编译器都是使用栈来实现递归的,当调用一个方法的时候编译器会将参数和返回地址压入栈中,然后把控制转移给这个方法,当方法返回时,这些值退栈,参数小时。

 

下面是模拟的递归的过程:

package digui;

public class XiaoDigui{
	static int theNumber;
	static int theAnswer;
	static StackX theStack;
	static int codePart;
	static Params theseParams;
	
	public static void main(String[] args) {
		theNumber = 3;
		recTriangle();
		System.out.println("Triangle = " + theAnswer);
	}
	
	
	/**
	 * 初始化信息
	 */
	public static void recTriangle(){
		theStack = new StackX(10000);
		codePart = 1;
		while (step() == false){
			;
		}
	}
	
	public static boolean step(){
		switch (codePart){
		
			//初始的参数压入栈中,返回地址为步骤6.下一步为步骤2
			case 1:
				theseParams = new Params(theNumber, 6);
				theStack.push(theseParams);
				codePart = 2;
				break;
				
			/**
			 * 判断参数是否已经达到最小值1,如果达到则返回最小值并且跳转步骤5,
			 * 反之则将参数N-1 以及返回位置4 压入栈中。并且跳转步骤3
			 */
			case 2:
				theseParams = theStack.peek();
				if (theseParams.n == 1){
					 theAnswer = 1;
					 codePart = 5;
				}else{
					codePart = 3;
				}
				break;
				
			//将n-1的参数以及返回位置4压入栈中,跳转步骤2
			case 3:
				Params newParams = new Params(theseParams.n - 1, 4);
				theStack.push(newParams);
				codePart = 2;
				break;
				
			//将栈中的参数对象取出,将要获取的值做叠加操作。跳转步骤5
			case 4:
				theseParams = theStack.peek();
				theAnswer = theAnswer + theseParams.n;
				codePart = 5;
				break;
			
			//取出栈中首个参数对象赋予当前对象,然后销毁取出的对象。跳转步骤4
			case 5:
				theseParams = theStack.peek();
				codePart = theseParams.returnAddress;
				theStack.pop();
				break;
				
			//返回true 循环操作。
			case 6:
				return true;
		}
		return false;
	}
}

/**
 * 栈,用于存放参数对象的 
 */
class StackX{
	private int maxSize;
	private Params[] stackArray;
	private int top;
	
	public StackX(int s){
		maxSize = s;
		stackArray = new Params[maxSize];
		top = -1;
	}
	
	//入栈
	public void push(Params p){
		stackArray[++top] = p;
	}
	
	//销毁对象
	public Params pop(){
		return stackArray[top--];
	}
	
	//取出参数对象
	public Params peek(){
		return stackArray[top];
	}
}

/**
 * 参数对象
 */
class Params {
	public int n;
	public int returnAddress;
	
	public Params(int nn, int ra){
		n = nn;
		returnAddress = ra;
	}
}

 

 

递归------消除递归(递归原理解析)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号