ITPub博客

首页 > 应用开发 > Java > AJPFX:递归与非递归之间的转化

AJPFX:递归与非递归之间的转化

Java 作者:AJPFX 时间:2019-05-14 11:56:35 0 删除 编辑
在常规表达式求值中:
输入为四则运算表达式,仅由数字、+、-、*、/ 、(、) 组成,没有空格,要求求其值.
我们知道有运算等级,从左至右,括号里面的先运算,其次是* 、/,再是+、- ;
这样我们就可以用递归来表达这
     这样就可以用递归来描述了
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.用栈实现快速排序


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69920205/viewspace-2644269/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2019-05-03

  • 博文量
    65
  • 访问量
    45884