在常规表达式求值中:
输入为四则运算表达式，仅由数字、+、－、*、/ 、(、) 组成，没有空格，要求求其值.
我们知道有运算等级，从左至右，括号里面的先运算，其次是* 、/,再是+、- ；
这样我们就可以用递归来表达这个式子了：
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;
}
}
}
}
相关推荐
递归与非递归的相互转化以及各自的时间效率相比较，各自在实际中的应用举例
快速排序算法设计与分析总结 二叉树与树的转换前序、后序的递归、非递归算法，层次序的非递归算法的实现 二叉树与树的转换前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现 实现树与...
实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。
递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序、中序和后序。第一篇就是关于这三种遍历方法的递归和非递归算法。
这个分类里面不好选，有可能选错分类了，但是如果你学编程，一定要学数据结构与算法的。递归很好用，也很难用。
20二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。（2 人） 要求： 树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历...
递归算法到非递归算法的转换,递归算法到非递归算法的转换。
递归算法转为非递归算法。方法、过程，用栈的原理
利用栈来消除递归 模拟快速排序的过程 实现非递归的快速排序
浅谈 递归机制 非递归 转换 txt
递归算法与非递归算法的转换文.pdf
⒈ 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现； ⒉ 树与二叉树的转换的实现。
演示了如何把低效率的递归函数转换成非递归的函数并完成相同的计算。
递归算法的非递归实现，教你如何将一个递归算法转化为一个非递归算法
递归小结 •优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的...◦通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。
常用的数据结构的算法，包括二叉树的三种递归和非递归算法，染色问题，八皇后问题，深度广度遍历，约瑟夫环，数值转换，树的高度和叶子节点数，最小生成树 ，两点之间的所有路径
对于一个无向连通图，从图中某一顶点出发，...然而图的深度优先搜索（DFS）算法一般采用递归算法来实现，鉴于二叉树遍历算法可以转换为非递归算法来实现，试编写基于DFS的非递归遍历算法的无向图的连通分量的识别程序。
* 情况下，把递归算法转换成非递归的算法是非常有用的，这种转换经常用到栈。 * * 递归和栈： * 递归和栈之间有着紧密的联系，大部分的编译器使用栈实现递归的。 * * 调用方法的时候发生什么： * 1. ...
递归向非递归的转换问题一直是一个容易忽视的问题，所以重新整理了一下供大家批评指教
常用的数据结构的算法，包括二叉树的三种递归和非递归算法，染色问题，八皇后问题，深度广度遍历，约瑟夫环，数值转换，树的高度和叶子节点数，最小生成树 ，两点之间的所有路径