在常规表达式求值中:
输入为四则运算表达式，仅由数字、+、－、*、/ 、(、) 组成，没有空格，要求求其值.
我们知道有运算等级，从左至右，括号里面的先运算，其次是* 、/,再是+、- ；
这样我们就可以用递归来表达这个式子了：
1. 
2.
3. 
这样就可以用递归来描述了
1.
/**
求一个因子的值
*/
double factor_value(){
double result = 0 ;
char c = cin.peek();//从cin看一个字符，不取出
if(c=='('){
cin.get();
result = expression_value() ;
cin.get();
}
else{
while(isdigit(c))//检查参数c是否为阿拉伯数字0到9
{
result = 10*result + c - '0' ;
cin.get() ;
c = cin.peek();
}
}
return result ;
}
2.
/**
求一个项的值
*/
double term_value()
{
double result = factor_value() ;//求第一个因子的值
bool more = true ;
while(more){
char op = cin.peek() ;
if(op=='*'||op=='/'){
cin.get() ;
int value = factor_value() ;
if(op == '*') result*= value ;
else result /= value ;
}
else more = false ;
}
return result ;
}
3.
/**
求一个表达式的值
*/
double expression_value(){
double result = term_value() ;//求第一项的值
bool more = true ;
while(more){
char op = cin.peek() ;
if(op=='+'||op=='-'){
cin.get() ;
int value = term_value() ;
if(op == '+') result+= value ;
else result -= value ;
}
else more = false ;
}
return result ;
}
4.
#include<iostream>
using namespace std ;
double factor_value();//因子
double term_value();//项
double expression_value();//表达式
int main()
{
cout << expression_value() << endl;
return 0 ;
}
总结下递归的优缺点：
优点：直接、简捷、算法程序结构清晰、思路明了。
缺点：递归的执行过程很让人头疼。
下面我们就用栈来替代上面的递归程序：
首先理解栈的概念：栈是一种应用范围广泛的数据结构，适用于各种具有“后进先出”特性的问题。
栈与过程调用：
1.考虑下面三个过程：
public void A1(){
begin :
........
r: b();
.........
endl ;
}
public void A2(){
begin :
........
t: c();
.........
endl ;
}
public void A3(){
begin :
........
endl ;
}
过程A1在其过程体的某一处调用过程A2，A2以在其过程体的某一处调用过程A3，A3不调用其他过程。
当过程A1执行到的r处时，它自己实际上被"挂起来，而被调用过程A2开始运行。一直等到A2执行完毕这后才返回过程A1的r1处继续执行A1剩下部分。 在过程A2的上述运行中，由于调用了A3，A2同样在t处"挂"起并一直等到A3执行结束后返回t1处才能继续执行后继语句。
2.嵌套调用过程中调用关系
3.相应工作栈的变化
遇到一个过程调用便立刻将相应的返回位置(及其它有用的信息)进栈；每当一被调用过程执行结束时，工作栈栈顶元素下好是此过程的返回位置。
就以上面的常规表达式为例：
例： 1+（3-2）*4/2
步骤 OPTR栈 OPND栈 输入字符 主要操作
1 # 1 PUSH(OPND,'1')
2 # 1 + PUSH(OPTR,'+')
3 #+ 1 ( PUSH(OPTR,'(')
4 #+( 1 3 PUSH(OPND,'3')
5 #+( 13 - PUSH(OPTR,'-')
6 #+(- 13 2 PUSH(OPND,'2')
7 #+(- 132 ) operate('3','-','2')
8 #+( 11 POP(OPTR){消去一对括号}
9 #+ 11 * PUSH(OPTR,'*')
10 #+* 11 4 PUSH(OPND,'4')
11 #+* 114 / operate('1','*','4')
12 #+ 14 PUSH(OPTR,'/')
12 #+/ 14 2 PUSH(OPND,'2')
13 #+/ 142 # PUSH(OPND,'#')
14 #+/ 142 operate('4','/','2')
15 #+ 12 operate('1','+','2')
16 # 3 return(GetTop(OPND));
4.为什么要学习递归与非递归的转换方法:
并不是每一门语言都支持递归的
有助于理解递归的本质
有助于理解栈,树等数据结构
一般来说，递归时间复杂度和对应的非递归差不多，但是递归的效率是相当低，它主要花费在反复的进栈出栈，各种中断等机制上，更有甚者，在递归求解过程中，某些解会重复的求好几次。
5.递归与非递归转换的原理
简单递归一般就是根据递归式来找出递推公式，即引入循环、递归调用树来模拟递归
复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回溯点来求解。
举个例子：在快速排序中，就可以清晰的理解其中的道理。
我还是用Java还举这个例子吧，不用G++了
1.用递归实现快速排序
package dsa;
/**
* 快速排序
* @author tanlvxu
*
*/
public class Demo21 {
/**
* @param args
*/
public static void main(String[] args) {
int a[]={4,3,2,5} ;
new Demo21().qSort_Init(a, 0, 3) ;
for(int i=0;i<=3;i++)
System.out.print(a[i]) ;
}
public void swap(int a[],int low,int high)
{
int temp = a[low] ;
a[low] = a[high] ;
a[high] = temp ;
}
public int qSort(int a[],int low,int high)
{
int p = a[low] ;
while(low<high)
{
while(low<high && a[high]>=p)
{
high-- ;
}
swap(a,low,high) ;
while(low<high && a[high]<=p)
{
low++ ;
}
swap(a,low,high) ;
}
return low ;
}
public void qSort_Init(int a[],int low,int high)
{
int p ;
if(low<high)
{
p = qSort(a,low,high);
qSort_Init(a,low,p-1);
qSort_Init(a,p+1,high);
}
}
}
2.用栈实现快速排序
package dsa;
/**
* 用栈实现快速排序
* @author tanlvxu
*
*/
public class Demo22 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={4,3,2,5} ;
new Demo22().qSort_Init(a, 0, 3) ;
for(int i=0;i<=3;i++)
System.out.print(a[i]) ;
}
public void swap(int a[],int low,int high)
{
int temp = a[low] ;
a[low] = a[high] ;
a[high] = temp ;
}
public int qSort(int a[],int low,int high)
{
int p = a[low] ;
while(low<high)
{
while(low<high && a[high]>=p)
{
high-- ;
}
swap(a,low,high) ;
while(low<high && a[high]<=p)
{
low++ ;
}
swap(a,low,high) ;
}
return low ;
}
public void qSort_Init(int a[],int low,int high)
{
int m[] = new int[100] ;
int n[] = new int[100] ;
int cp,p,sublow,subhigh ;
/*
* 初始化栈和栈顶指针
*/
m[0] = low ;
n[0] = high ;
cp = 0 ;
while(cp>=0){
sublow = m[cp] ;
subhigh = n[cp] ;
cp -- ;
if(sublow<subhigh){
p = qSort(a, sublow, subhigh) ;
cp ++ ;
m[cp] = sublow ;
n[cp] = p-1 ;
cp++ ;
m[cp] = p + 1;
n[cp] = subhigh;
}
}
}
}
相关推荐
递归算法与非递归转化 递归算法是把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数（或过程）来表示问题的解。递归的效率一般不高，但是递归比较符合人类的思维方式。一般而言非递归算法更有效；但很多...
快速排序算法设计与分析总结 二叉树与树的转换前序、后序的递归、非递归算法，层次序的非递归算法的实现 二叉树与树的转换前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现 实现树与...
"递归与非递归转换的基础知识" 一、为什么要学习递归与非递归的转换的实现方法？ 学习递归与非递归的转换是非常重要的，因为它可以帮助我们更好地理解递归和栈这两个重要的数据结构。首先，不是所有的编程语言都...
根据给定文件的信息，本文将详细介绍二叉树与树之间的转换方法，并且深入探讨树的前序、中序、后序遍历递归与非递归实现方式，以及层次遍历的非递归算法实现。 ### 二叉树与树的转换 在计算机科学中，树是一种常用...
非递归实现的基本思想是将递归调用转化为循环，并使用数据结构（如堆栈）存储中间结果，避免了递归带来的调用栈溢出问题。 非递归实现的步骤大致如下： 1. 初始化一个堆栈，用于保存待处理的阿克曼函数参数对`(m, ...
本章将探讨如何将递归算法转换为非递归算法。 首先，我们要了解递归的定义。递归发生在一个过程或函数在定义中调用自身，这被称为直接递归。如果一个过程调用另一个，而后者又调用前者，那么这是间接递归。例如，...
20二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（2 人） 要求： 树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历...
非递归实现快速排序的关键在于使用栈来模拟递归调用的过程。在递归版本中，我们首先选择一个基准元素（pivot），然后将数组分为两部分：小于基准的元素和大于或等于基准的元素。接着对这两部分分别进行递归排序。非...
递归算法转为非递归算法。方法、过程，用栈的原理
在计算机科学与编程领域中，递归算法与非递归算法是两种非常重要的计算方法。本文将详细介绍这两种算法的特点、应用场景以及如何实现它们，特别针对初学者及面试准备者。 #### 递归算法 递归算法是一种直接或间接...
与递归下降解析器通过函数调用实现语法分析不同，非递归预测分析使用栈来存储符号，并基于当前输入符号和栈顶符号的状态来决定下一步的操作。这种方法也被称为LR（Left-to-Right, Rightmost-derivation）分析，因为...
通过以上分析，我们可以看到，阿克曼函数的非递归实现主要涉及堆栈操作、递归转换以及对计算复杂性的理解。这个话题对于学习数据结构和算法的学生来说，是一个挑战性的实践项目，有助于提升他们的编程技能和对复杂...
**递归算法与非递归算法的转换** 递归算法是一种强大的编程技术，它通过将问题分解成规模更小的相同问题来解决复杂问题。在递归算法中，函数或过程会直接或间接地调用自身，直到遇到一个基本的终止条件，即递归出口...
根据给定文件的信息，我们可以提炼出递归机制与非递归转换的相关知识点： ### 递归机制 #### 定义 ...通过对递归原理的理解和掌握，以及对递归与非递归之间的转换，可以帮助我们更好地解决复杂问题。
在计算机科学中，数据结构是组织和管理数据的方式，它直接影响到程序的效率和性能。栈是一种特殊的数据结构，...理解并掌握如何将递归转化为非递归，不仅可以提升代码质量，也是成长为一名优秀程序员的关键技能之一。
本压缩包包含的是关于树的遍历，特别是递归和非递归实现方式的工程源码，这些代码基于C++语言，存放在Dep工程文件夹中。 首先，我们要理解什么是树的遍历。树遍历是指按照特定顺序访问树的所有节点。通常，有三种...
本话题聚焦于使用MFC（Microsoft Foundation Classes）库在C++环境中实现树的各种遍历算法，包括先序、中序和后序遍历，既可以通过递归方式，也可以采用非递归方法。 首先，我们来理解树的基本概念。树由节点和边...
非递归算法通常通过使用数据结构（如栈）来模拟递归过程，从而避免了递归调用带来的额外开销。 首先，我们需要创建一个栈来存储盘子的状态。栈将用于保存每个盘子的移动顺序，以便在适当的时候回溯。在C++中，可以...
贺存薪提出的非递归算法的核心是通过观察递归算法中的移动规律，并将其转化为一系列确定性的操作。通过这种方式，可以有效地避免递归调用所带来的额外开销，从而提高算法的整体效率。 ##### C++实现 非递归算法的...