在常規(guī)表達式求值中:

輸入為四則運算表達式，僅由數(shù)字、+、－、*、/ 、(、) 組成，沒有空格，要求求其值.

我們知道有運算等級，從左至右，括號里面的先運算，其次是* 、/,再是+、- ；

這樣我們就可以用遞歸來表達這

     這樣就可以用遞歸來描述了

1.   3  

4.    總結(jié)下遞歸的優(yōu)缺點：

    優(yōu)點：直接、簡捷、算法程序結(jié)構(gòu)清晰、思路明了。

    缺點：遞歸的執(zhí)行過程很讓人頭疼。

下面我們就用棧來替代上面的遞歸程序：

首先理解棧的概念：棧是一種應用范圍廣泛的數(shù)據(jù)結(jié)構(gòu)，適用于各種具有“后進先出”特性的問題。

棧與過程調(diào)用：

  1.考慮下面三個過程：

     public void A1(){

     begin :

      ........   

      r: b();

     .........

      endl ;

     }

     public void A2(){

       begin :

      ........   

      t: c();

     .........

      endl ;

      }

      public void A3(){

           begin :

            ........   

           endl ;

      }

過程A1在其過程體的某一處調(diào)用過程A2，A2以在其過程體的某一處調(diào)用過程A3，A3不調(diào)用其他過程。

當過程A1執(zhí)行到的r處時，它自己實際上被"掛起來，而被調(diào)用過程A2開始運行。一直等到A2執(zhí)行完畢這后才返回過程A1的r1處繼續(xù)執(zhí)行A1剩下部分。 在過程A2的上述運行中，由于調(diào)用了A3，A2同樣在t處"掛"起并一直等到A3執(zhí)行結(jié)束后返回t1處才能繼續(xù)執(zhí)行后繼語句。

3.相應工作棧的變化

    遇到一個過程調(diào)用便立刻將相應的返回位置(及其它有用的信息)進棧；每當一被調(diào)用過程執(zhí)行結(jié)束時，工作棧棧頂元素下好是此過程的返回位置。
就以上面的常規(guī)表達式為例：

        例： 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.為什么要學習遞歸與非遞歸的轉(zhuǎn)換方法:

并不是每一門語言都支持遞歸的
有助于理解遞歸的本質(zhì)
有助于理解棧,樹等數(shù)據(jù)結(jié)構(gòu)
一般來說，遞歸時間復雜度和對應的非遞歸差不多，但是遞歸的效率是相當?shù)?，它主要花費在反復的進棧出棧，各種中斷等機制上，更有甚者，在遞歸求解過程中，某些解會重復的求好幾次。

5.遞歸與非遞歸轉(zhuǎn)換的原理
簡單遞歸一般就是根據(jù)遞歸式來找出遞推公式，即引入循環(huán)、遞歸調(diào)用樹來模擬遞歸
復雜遞歸一般就是模擬系統(tǒng)處理遞歸的機制，使用?；蜿犃械葦?shù)據(jù)結(jié)構(gòu)保存回溯點來求解。

舉個例子：在快速排序中，就可以清晰的理解其中的道理。

我還是用Java還舉這個例子吧，不用G++了

1.用遞歸實現(xiàn)快速排序

  2.用棧實現(xiàn)快速排序