AJPFX:遞歸與非遞歸之間的轉化
在常規表達式求值中:
輸入為四則運算表達式，僅由數字、+、－、*、/ 、(、) 組成，沒有空格，要求求其值.
我們知道有運算等級，從左至右，括號里面的先運算，其次是* 、/,再是+、- ；
這樣我們就可以用遞歸來表達這
這樣就可以用遞歸來描述了
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.用棧實現快速排序
