遞歸算法實際上是一種分而治之的方法,它把復雜問題分解為簡單問題來求解。對於某些復雜問題(例如hanio塔問題),遞歸算法是一種自然且合乎邏輯的解決問題的方式,但是遞歸算法的執行效率通常比較差。因此,在求解某些問題時,常采用遞歸算法來分析問題,用非遞歸算法來求解問題;另外,有些程序設計語言不支持遞歸,這就需要把遞歸算法轉換為非遞歸算法。
將遞歸算法轉換為非遞歸算法有兩種方法,一種是直接求值(迭代/循環),不需要回溯;另一種是不能直接求值,需要回溯。前者使用一些變量保存中間結果,稱為直接轉換法;後者使用棧保存中間結果,稱為間接轉換法,下面分別討論這兩種方法。
C++遞歸求解N個元素的所有子集 http://www.linuxidc.com/Linux/2014-02/96222.htm
C語言實現二叉樹的遞歸遍歷與非遞歸遍歷 http://www.linuxidc.com/Linux/2013-11/92544.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
1. 直接轉換法
直接轉換法通常用來消除尾遞歸和單向遞歸,將遞歸結構用循環結構來替代。
單向遞歸:簡單的說是指遞歸的過程總是朝著一個方向進行,如果函數1調用了函數2,而函數2又調用了函數1,則這種情況不屬於單向遞歸。斐波那契數列的遞歸求解可轉用一個迭代法實現。
斐波那契數列的遞歸求解:
int Fib(int n) {
if(n <= 1) return n;
else return Fib(n - 1) + Fib(n - 2);
}
轉化為迭代求解:
int Fib(int n) {
if(n <= 1) return n;
int twoBack = 0;
int oneBack = 1;
int cur;
for(int i = 2;i < = n; i++) {
cur = twoBack + oneBack;
twoBack = oneBack;
oneBack = cur;
}
return cur;
}
尾遞歸函數是以遞歸調用結尾的函數,是單向遞歸的特例。它的遞歸調用語句只有一個,而且是放在過程的最後。當遞歸調用返回時,返回到上一層遞歸調用語句的下一語句,而這個位置正好是程序的結尾,因此遞歸工作棧中可以不保存返回地址;除了返回值和引用值外,其他參數和局部變量都不再需要,因此可以不用棧,直接采用循環寫出非遞歸過程。
階乘函數就不是一個尾遞歸。因為在它收到遞歸調用的結果後,必須在返回調用前再做一次乘法運算。但是階乘函數可以轉化成一個尾遞歸函數,例:
階乘的遞歸求解:
int factorial(int n)
{
if(n == 0) return 1;
else
{
int val = factorial(n - 1);
return n * val;
}
}
轉化為尾遞歸求解:
int factorial(int acc, int x)
{ //acc傳的值為1。
if(x <= 1) return acc;
else
return factorial(x * acc, x - 1);
}
尾遞歸的重要性在於當進行尾遞歸調用時,調用者的返回位置不需要被存在調用棧裡。當遞歸調用返回時,它直接分支到先前已保存的返回地址。因此,在支持尾遞歸優化的編譯器上,尾遞歸在時間和空間上都比較劃算。迭代算法需要一個臨時變量,這無疑導致了程序的可讀性降低,迭代函數不像遞歸函數那樣需要考慮函數調用的支出,而且對一個線程來說可用的棧空間通常比可用的堆空間要少得多,而遞歸算法則相對迭代算法需要更多的棧空間!
2. 間接轉換法
該方法使用棧保存中間結果,一般需根據遞歸函數在執行過程中棧的變化得到。其一般過程如下:
將初始狀態s0進棧
while (棧不為空)
{
退棧,將棧頂元素賦給s;
if (s是要找的結果) 返回;
else {
尋找到s的相關狀態s1;
將s1進棧
}
}
間接轉換法在數據結構中有較多實例,如二叉樹遍歷算法的非遞歸實現、圖的深度優先遍歷算法的非遞歸實現等等,請讀者參考主教材中相關內容。