在常规表达式求值中:
输入为四则运算表达式，仅由数字、+、－、*、/ 、(、) 组成，没有空格，要求求其值.
我们知道有运算等级，从左至右，括号里面的先运算，其次是* 、/,再是+、- ；
这样我们就可以用递归来表达这
这样就可以用递归来描述了
1. 3
4. 总结下递归的优缺点：
优点：直接、简捷、算法程序结构清晰、思路明了。
缺点：递归的执行过程很让人头疼。
下面我们就用栈来替代上面的递归程序：
首先理解栈的概念：栈是一种应用范围广泛的数据结构，适用于各种具有“后进先出”特性的问题。
栈与过程调用：
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处才能继续执行后继语句。
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.用递归实现快速排序
2.用栈实现快速排序
收藏
淘帖
踩
