递归原理:大部分编译器都是使用栈来实现递归的,当调用一个方法的时候编译器会将参数和返回地址压入栈中,然后把控制转移给这个方法,当方法返回时,这些值退栈,参数小时。
下面是模拟的递归的过程:
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-1-课程内容和安排介绍1-1-计算机的概念1...函数与递归-1-函数定义第6章-函数与递归-2-函数的调用和返回值第6章-函数与递归-3-改变参数值的函数第6章-函数与递归-4-程序结构和递归第6章-函数与递归-5-函数实例
该程序能够处理基本的数学运算,包括加法、减法、乘法和除法,并通过递归的方式解析和计算表达式。 #### 主要知识点 ##### 1. **递归算法在计算器中的应用** - **递归的基本概念**:递归是一种通过函数调用自身...
基础算法-递归-杨鑫20191010.pptx,基础算法-递归-杨鑫20191010.pptx,基础算法-递归-杨鑫20191010.pptx
本资料“栈与递归--含分治与回溯”深入探讨了这两个主题,并将它们与分治策略和回溯法相结合,提供了一种高效解决问题的方法。 首先,栈是一种特殊的线性数据结构,遵循后进先出(LIFO)的原则。在计算机程序中,栈...
数据结构:栈与递归--含分治与回溯.ppt
java语法 method 递归 马克-to-win java视频 方法 重载
本文将通过实验和代码实现,来详细介绍递归算法的原理和应用。 一、递归算法的原理 递归算法的核心思想是将问题分解成更小的子问题,然后使用同样的方法解决这些子问题。这个过程可以继续下去,直到问题的规模小到...
c++代码-递归-快速排序
工具类库-Excel-编号生成-Session共享-定时任务-递归-EF扩展
【栈与递归】 栈是一种特殊的线性数据结构,具有后进先出(LIFO)的特点,常用于实现函数调用的过程。在计算机程序中,每当一个函数被调用时,系统会在栈中为该函数创建一个新的栈帧,保存其局部变量和返回地址等...
在编译原理中,消除文法的左递归是一个重要的概念,主要应用于解析器的构造。这个过程是为了使解析过程更加高效,避免无限循环的发生。本文将深入探讨左递归的定义、为何需要消除以及如何消除,同时结合课程设计与...
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
在这个主题“递归实现的表达式计算”中,我们将深入探讨如何使用递归方法解析和计算数学表达式。递归的核心思想是解决问题的子问题与原问题具有相同的形式,因此可以通过调用自身来解决。 首先,我们要理解表达式...
在编译原理中,消除左递归是一种优化技术,用于改进词法分析器(也称为扫描器或分词器)和语法分析器(通常为LR或LL解析器)的性能。左递归可能会导致无限递归,使得解析过程无法终止,因此识别并消除它是编译器设计...
#### 标题:大学计算机第3讲-程序与递归-组合-抽象与构造 #### 描述:大学计算机第3讲-程序与递归-组合-抽象与构造 #### 标签:无 #### 部分内容概述: 本次课程主要围绕着“程序与递归”的主题展开讨论,具体...
数据结构(c语言) 对于汉诺塔的递归实现。在对学习数据结构递归的人,帮助他们对汉诺塔和递归思想的理解
在编译原理中,消除左递归是一项重要的技术,它主要应用于构造上下文无关文法(Context-Free Grammar, CFG)的过程中。...消除左递归是编译器设计的基础,对于理解编译原理和提升解析性能至关重要。