在常规表达式求值中: 输入为四则运算表达式，仅由数字、+、－、*、/ 、(、) 组成，没有空格，要求求其值. 我们知道有运算等级，从左至右，括号里面的先运算，其次是* 、/,再是+、- ； 这样我们就可以用递归来表达这      这样就可以用递归来描述了 1.   3   4.    总结下递归的优缺点：     优点：直接、简捷、算法程序结构清晰、思路明了。     缺点：递归的执行过程很让人头疼。

 

下面我们就用栈来替代上面的递归程序： 首先理解栈的概念：栈是一种应用范围广泛的数据结构，适用于各种具有“后进先出”特性的问题。

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 栈与过程调用：   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.用栈实现快速排序
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄