`
12616383
  • 浏览: 51241 次
  • 性别: Icon_minigender_1
  • 来自: 待定
社区版块
存档分类
最新评论

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

 
阅读更多

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

 

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

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;
	}
}

 

 

分享到:
评论

相关推荐

    文件递归-XML递归-树图递归

    ### 文件递归-XML递归-树图递归 #### 一、文件系统递归 在计算机科学中,文件系统递归是指通过遍历文件系统(通常是从根目录开始)来处理目录及其子目录下的所有文件的过程。这种方法常用于搜索特定类型的文件、...

    递归-----动态树实现递归

    标题“递归-----动态树实现递归”暗示我们将探讨如何利用递归方法来操作动态树。 首先,让我们理解什么是动态树。动态树,顾名思义,是一种可以随程序运行而改变结构的树形数据结构。与静态树不同,它的节点可以在...

    Python语言程序设计教程 北理工Python课程第6章-函数与递归-4-程序结构和递归 共20页.pdf

    【大纲】0-1-课程内容和安排介绍1-1-计算机的概念1...函数与递归-1-函数定义第6章-函数与递归-2-函数的调用和返回值第6章-函数与递归-3-改变参数值的函数第6章-函数与递归-4-程序结构和递归第6章-函数与递归-5-函数实例

    计算器递归----c++

    该程序能够处理基本的数学运算,包括加法、减法、乘法和除法,并通过递归的方式解析和计算表达式。 #### 主要知识点 ##### 1. **递归算法在计算器中的应用** - **递归的基本概念**:递归是一种通过函数调用自身...

    基础算法-递归-杨鑫20191010.pptx

    基础算法-递归-杨鑫20191010.pptx,基础算法-递归-杨鑫20191010.pptx,基础算法-递归-杨鑫20191010.pptx

    栈与递归--含分治与回溯.zip

    本资料“栈与递归--含分治与回溯”深入探讨了这两个主题,并将它们与分治策略和回溯法相结合,提供了一种高效解决问题的方法。 首先,栈是一种特殊的线性数据结构,遵循后进先出(LIFO)的原则。在计算机程序中,栈...

    数据结构:栈与递归--含分治与回溯.ppt

    数据结构:栈与递归--含分治与回溯.ppt

    java-c语法7---method-递归---马克-to-win java视频

    java语法 method 递归 马克-to-win java视频 方法 重载

    算法基础与递归-百积问题-递归求公约数-求阶乘-斐波那契数列

    本文将通过实验和代码实现,来详细介绍递归算法的原理和应用。 一、递归算法的原理 递归算法的核心思想是将问题分解成更小的子问题,然后使用同样的方法解决这些子问题。这个过程可以继续下去,直到问题的规模小到...

    c++代码-递归-快速排序

    c++代码-递归-快速排序

    栈与递归--含分治与回溯.ppt

    【栈与递归】 栈是一种特殊的线性数据结构,具有后进先出(LIFO)的特点,常用于实现函数调用的过程。在计算机程序中,每当一个函数被调用时,系统会在栈中为该函数创建一个新的栈帧,保存其局部变量和返回地址等...

    消除文法左递归

    在编译原理中,消除文法的左递归是一个重要的概念,主要应用于解析器的构造。这个过程是为了使解析过程更加高效,避免无限循环的发生。本文将深入探讨左递归的定义、为何需要消除以及如何消除,同时结合课程设计与...

    n后问题---递归回溯法 n后问题---递归回溯法

    n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...

    递归实现的表达式计算

    在这个主题“递归实现的表达式计算”中,我们将深入探讨如何使用递归方法解析和计算数学表达式。递归的核心思想是解决问题的子问题与原问题具有相同的形式,因此可以通过调用自身来解决。 首先,我们要理解表达式...

    编译原理之之消除左递归

    在编译原理中,消除左递归是一种优化技术,用于改进词法分析器(也称为扫描器或分词器)和语法分析器(通常为LR或LL解析器)的性能。左递归可能会导致无限递归,使得解析过程无法终止,因此识别并消除它是编译器设计...

    大学计算机第3讲-程序与递归-组合-抽象与构造.ppt

    #### 标题:大学计算机第3讲-程序与递归-组合-抽象与构造 #### 描述:大学计算机第3讲-程序与递归-组合-抽象与构造 #### 标签:无 #### 部分内容概述: 本次课程主要围绕着“程序与递归”的主题展开讨论,具体...

    数据结构(c语言)---递归---Hanno.cpp

    数据结构(c语言) 对于汉诺塔的递归实现。在对学习数据结构递归的人,帮助他们对汉诺塔和递归思想的理解

    汉诺塔-非递归-java程序代码+实验报告

    它帮助理解算法的工作原理以及其实效性。 6. **项目结构**:`.classpath`是Eclipse项目配置文件,`.project`是项目的元数据,`bin`目录存放编译后的class文件,`src`是源代码目录,`images`可能包含与实验报告相关...

Global site tag (gtag.js) - Google Analytics