摘要：我們經常會用到遞歸函數，但是如果遞歸深度太大時，往往導致棧溢出。而遞歸深度往往不太容易把握，所以比較安全一點的做法就是：用循環代替遞歸。文章最后的原文里面講了如何用10步實現這個過程，相當精彩。本文翻譯了這篇文章，并加了自己的一點注釋和理解。

?

目錄

?簡介

模擬函數的目的

遞歸和模擬函數的優缺點

用棧和循環代替遞歸的10個步驟

替代過程的幾個簡單例子

更多的例子

結論

參考

協議

1?簡介

　　一般我們在進行排序(比如歸并排序)或者樹操作時會用到遞歸函數。但是如果遞歸深度達到一定程度以后，就會出現意想不到的結果比如堆棧溢出。雖然有很多有經驗的開發者都知道了如何用循環函數或者棧加while循環來代替遞歸函數，以防止棧溢出，但我還是想分享一下這些方法，這或許會對初學者有很大的幫助。

2?模擬函數的目的

　　如果你正在使用遞歸函數，并且沒有控制遞歸調用，而棧資源又比較有限，調用層次過深的時候就可能導致棧溢出/堆沖突。模擬函數的目的就是在堆中開辟區域來模擬棧的行為，這樣你就能控制內存分配和流處理，從而避免棧溢出。如果能用循環函數來代替效果會更好，這是一個比較需要時間和經驗來處理的事情，出于這些原因，這篇文章為初學者提供了一個簡單的參考，怎樣使用循環函數來替代遞歸函數，以防止棧溢出？

3 遞歸函數和模擬函數的優缺點

　　遞歸函數：

　　優點：算法比較直觀。可以參考文章后面的例子

　　缺點：可能導致棧溢出或者堆沖突

　　你可以試試執行下面兩個函數(后面的一個例子)，IsEvenNumber(遞歸實現)和IsEvenNumber(模擬實現)，他們在頭文件"MutualRecursion.h"中聲明。你可以將傳入參數設定為10000，像下面這樣：

#include "MutualRecursion.h" bool result = IsEvenNumberLoop(10000); // 成功返回bool result2 = IsEvenNumber(10000); // 會發生堆棧溢出

?有些人可能會問：如果我增加棧的容量不就可以避免棧溢出嗎？好吧，這只是暫時的解決問題的辦法，如果調用層次越來越深，很有可能會再次發生溢出。

?　　模擬函數：

　　優點：能避免棧溢出或者堆沖突錯誤，能對過程和內存進行更好的控制

　　缺點：算法不是太直觀，代碼難以維護

?

4 用棧和循環代替遞歸的10個步驟

第一步

1?定義一個新的結構體Snapshot，用于保存遞歸結構中的一些數據和狀態信息

2?在Snapshot內部需要包含的變量有以下幾種：

　　A?一般當遞歸函數調用自身時，函數參數會發生變化。所以你需要包含變化的參數，引用除外。比如下面的例子中，參數n應該包含在結構體中，而retVal不需要。

void SomeFunc(int n, int &retVal);

　　B?階段性變量"stage"(通常是一個用來轉換到另一個處理分支的整形變量)，詳見第六條規則

　　C?函數調用返回以后還需要繼續使用的局部變量(一般在二分遞歸和嵌套遞歸中很常見)

代碼：

1 // Recursive Function "First rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 17 // Conversion to Iterative Function 18 int SomeFuncLoop(int n, int &retIdx) 19 { 20 // (First rule) 21 struct SnapShotStruct { 22 int n; // - parameter input 23 int test; // - local variable that will be used 24 // after returning from the function call 25 // - retIdx can be ignored since it is a reference. 26 int stage; // - Since there is process needed to be done 27 // after recursive call. (Sixth rule) 28 }; 29 ... 30 }

?第二步

1?在函數的開頭創建一個局部變量，這個值扮演了遞歸函數的返回函數角色。它相當于為每次遞歸調用保存一個臨時值，因為C++函數只能有一種返回類型，如果遞歸函數的返回類型是void，你可以忽略這個局部變量。如果有缺省的返回值，就應該用缺省值初始化這個局部變量。

1 // Recursive Function "Second rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 // Conversion to Iterative Function 17 int SomeFuncLoop(int n, int &retIdx) 18 { 19 // (First rule) 20 struct SnapShotStruct { 21 int n; // - parameter input 22 int test; // - local variable that will be used 23 // after returning from the function call 24 // - retIdx can be ignored since it is a reference. 25 int stage; // - Since there is process needed to be done 26 // after recursive call. (Sixth rule) 27 }; 28 29 // (Second rule) 30 int retVal = 0; // initialize with default returning value 31 32 ... 33 // (Second rule) 34 return retVal; 35 }

?第三步

創建一個棧用于保存“Snapshot”結構體類型變量

1 // Recursive Function "Third rule" example2 3 // Conversion to Iterative Function4 int SomeFuncLoop(int n, int &retIdx)5 {6 // (First rule)7 struct SnapShotStruct {8 int n; // - parameter input9 int test; // - local variable that will be used 10 // after returning from the function call 11 // - retIdx can be ignored since it is a reference. 12 int stage; // - Since there is process needed to be done 13 // after recursive call. (Sixth rule) 14 }; 15 16 // (Second rule) 17 int retVal = 0; // initialize with default returning value 18 19 // (Third rule) 20 stack<SnapShotStruct> snapshotStack; 21 ... 22 // (Second rule) 23 return retVal; 24 }

?第四步

創建一個新的”Snapshot”實例，然后將其中的參數等初始化，并將“Snapshot”實例壓入棧

1 // Recursive Function "Fourth rule" example2 3 // Conversion to Iterative Function4 int SomeFuncLoop(int n, int &retIdx)5 {6 // (First rule)7 struct SnapShotStruct {8 int n; // - parameter input9 int test; // - local variable that will be used 10 // after returning from the function call 11 // - retIdx can be ignored since it is a reference. 12 int stage; // - Since there is process needed to be done 13 // after recursive call. (Sixth rule) 14 }; 15 16 // (Second rule) 17 int retVal = 0; // initialize with default returning value 18 19 // (Third rule) 20 stack<SnapShotStruct> snapshotStack; 21 22 // (Fourth rule) 23 SnapShotStruct currentSnapshot; 24 currentSnapshot.n= n; // set the value as parameter value 25 currentSnapshot.test=0; // set the value as default value 26 currentSnapshot.stage=0; // set the value as initial stage 27 28 snapshotStack.push(currentSnapshot); 29 30 ... 31 // (Second rule) 32 return retVal; 33 }

?第五步

寫一個while循環，使其不斷執行直到棧為空。在while循環的每一次迭代過程中，彈出”Snapshot“對象。

1 // Recursive Function "Fifth rule" example2 3 // Conversion to Iterative Function4 int SomeFuncLoop(int n, int &retIdx)5 {6 // (First rule)7 struct SnapShotStruct {8 int n; // - parameter input9 int test; // - local variable that will be used 10 // after returning from the function call 11 // - retIdx can be ignored since it is a reference. 12 int stage; // - Since there is process needed to be done 13 // after recursive call. (Sixth rule) 14 }; 15 // (Second rule) 16 int retVal = 0; // initialize with default returning value 17 // (Third rule) 18 stack<SnapShotStruct> snapshotStack; 19 // (Fourth rule) 20 SnapShotStruct currentSnapshot; 21 currentSnapshot.n= n; // set the value as parameter value 22 currentSnapshot.test=0; // set the value as default value 23 currentSnapshot.stage=0; // set the value as initial stage 24 snapshotStack.push(currentSnapshot); 25 // (Fifth rule) 26 while(!snapshotStack.empty()) 27 { 28 currentSnapshot=snapshotStack.top(); 29 snapshotStack.pop(); 30 ... 31 } 32 // (Second rule) 33 return retVal; 34 }

?第六步

將當前階段一分為二(針對當前只有單一遞歸調用的情形)。第一個階段代表了下一次遞歸調用之前的情況，第二階段代表了下一次遞歸調用完成并返回之后的情況(返回值已經被保存，并在此之前被累加)。

如果當前階段有兩次遞歸調用，就必須分為3個階段。階段1：第一次調用返回之前，階段2：階段1執行的調用過程。階段3：第二次調用返回之前。

如果當前階段有三次遞歸調用，就必須至少分為4個階段。

依次類推。

1 // Recursive Function "Sixth rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 // Conversion to Iterative Function 17 int SomeFuncLoop(int n, int &retIdx) 18 { 19 // (First rule) 20 struct SnapShotStruct { 21 int n; // - parameter input 22 int test; // - local variable that will be used 23 // after returning from the function call 24 // - retIdx can be ignored since it is a reference. 25 int stage; // - Since there is process needed to be done 26 // after recursive call. (Sixth rule) 27 }; 28 // (Second rule) 29 int retVal = 0; // initialize with default returning value 30 // (Third rule) 31 stack<SnapShotStruct> snapshotStack; 32 // (Fourth rule) 33 SnapShotStruct currentSnapshot; 34 currentSnapshot.n= n; // set the value as parameter value 35 currentSnapshot.test=0; // set the value as default value 36 currentSnapshot.stage=0; // set the value as initial stage 37 snapshotStack.push(currentSnapshot); 38 // (Fifth rule) 39 while(!snapshotStack.empty()) 40 { 41 currentSnapshot=snapshotStack.top(); 42 snapshotStack.pop(); 43 // (Sixth rule) 44 switch( currentSnapshot.stage) 45 { 46 case 0: 47 ... // before ( SomeFunc(n-1, retIdx); ) 48 break; 49 case 1: 50 ... // after ( SomeFunc(n-1, retIdx); ) 51 break; 52 } 53 } 54 // (Second rule) 55 return retVal; 56 }

?第七步

根據階段變量stage的值切換到相應的處理流程并處理相關過程。

1 // Recursive Function "Seventh rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 // Conversion to Iterative Function 17 int SomeFuncLoop(int n, int &retIdx) 18 { 19 // (First rule) 20 struct SnapShotStruct { 21 int n; // - parameter input 22 int test; // - local variable that will be used 23 // after returning from the function call 24 // - retIdx can be ignored since it is a reference. 25 int stage; // - Since there is process needed to be done 26 // after recursive call. (Sixth rule) 27 }; 28 29 // (Second rule) 30 int retVal = 0; // initialize with default returning value 31 32 // (Third rule) 33 stack<SnapShotStruct> snapshotStack; 34 35 // (Fourth rule) 36 SnapShotStruct currentSnapshot; 37 currentSnapshot.n= n; // set the value as parameter value 38 currentSnapshot.test=0; // set the value as default value 39 currentSnapshot.stage=0; // set the value as initial stage 40 41 snapshotStack.push(currentSnapshot); 42 43 // (Fifth rule) 44 while(!snapshotStack.empty()) 45 { 46 currentSnapshot=snapshotStack.top(); 47 snapshotStack.pop(); 48 49 // (Sixth rule) 50 switch( currentSnapshot.stage) 51 { 52 case 0: 53 // (Seventh rule) 54 if( currentSnapshot.n>0 ) 55 { 56 ... 57 } 58 ... 59 break; 60 case 1: 61 // (Seventh rule) 62 currentSnapshot.test = retVal; 63 currentSnapshot.test--; 64 ... 65 break; 66 } 67 } 68 // (Second rule) 69 return retVal; 70 }

?第八步

如果遞歸有返回值，將這個值保存下來放在臨時變量里面，比如retVal。當循環結束時，這個臨時變量的值就是整個遞歸處理的結果。

1 // Recursive Function "Eighth rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 // Conversion to Iterative Function 17 int SomeFuncLoop(int n, int &retIdx) 18 { 19 // (First rule) 20 struct SnapShotStruct { 21 int n; // - parameter input 22 int test; // - local variable that will be used 23 // after returning from the function call 24 // - retIdx can be ignored since it is a reference. 25 int stage; // - Since there is process needed to be done 26 // after recursive call. (Sixth rule) 27 }; 28 // (Second rule) 29 int retVal = 0; // initialize with default returning value 30 // (Third rule) 31 stack<SnapShotStruct> snapshotStack; 32 // (Fourth rule) 33 SnapShotStruct currentSnapshot; 34 currentSnapshot.n= n; // set the value as parameter value 35 currentSnapshot.test=0; // set the value as default value 36 currentSnapshot.stage=0; // set the value as initial stage 37 snapshotStack.push(currentSnapshot); 38 // (Fifth rule) 39 while(!snapshotStack.empty()) 40 { 41 currentSnapshot=snapshotStack.top(); 42 snapshotStack.pop(); 43 // (Sixth rule) 44 switch( currentSnapshot.stage) 45 { 46 case 0: 47 // (Seventh rule) 48 if( currentSnapshot.n>0 ) 49 { 50 ... 51 } 52 ... 53 // (Eighth rule) 54 retVal = 0 ; 55 ... 56 break; 57 case 1: 58 // (Seventh rule) 59 currentSnapshot.test = retVal; 60 currentSnapshot.test--; 61 ... 62 // (Eighth rule) 63 retVal = currentSnapshot.test; 64 ... 65 break; 66 } 67 } 68 // (Second rule) 69 return retVal; 70 }

?第九步

如果遞歸函數有“return”關鍵字，你應該在while循環里面用“continue”代替。如果return了一個返回值，你應該在循環里面保存下來(步驟8)，然后return。大部分情況下，步驟九是可選的，但是它能幫助你避免邏輯錯誤。

1 // Recursive Function "Ninth rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 // Conversion to Iterative Function 17 int SomeFuncLoop(int n, int &retIdx) 18 { 19 // (First rule) 20 struct SnapShotStruct { 21 int n; // - parameter input 22 int test; // - local variable that will be used 23 // after returning from the function call 24 // - retIdx can be ignored since it is a reference. 25 int stage; // - Since there is process needed to be done 26 // after recursive call. (Sixth rule) 27 }; 28 // (Second rule) 29 int retVal = 0; // initialize with default returning value 30 // (Third rule) 31 stack<SnapShotStruct> snapshotStack; 32 // (Fourth rule) 33 SnapShotStruct currentSnapshot; 34 currentSnapshot.n= n; // set the value as parameter value 35 currentSnapshot.test=0; // set the value as default value 36 currentSnapshot.stage=0; // set the value as initial stage 37 snapshotStack.push(currentSnapshot); 38 // (Fifth rule) 39 while(!snapshotStack.empty()) 40 { 41 currentSnapshot=snapshotStack.top(); 42 snapshotStack.pop(); 43 // (Sixth rule) 44 switch( currentSnapshot.stage) 45 { 46 case 0: 47 // (Seventh rule) 48 if( currentSnapshot.n>0 ) 49 { 50 ... 51 } 52 ... 53 // (Eighth rule) 54 retVal = 0 ; 55 56 // (Ninth rule) 57 continue; 58 break; 59 case 1: 60 // (Seventh rule) 61 currentSnapshot.test = retVal; 62 currentSnapshot.test--; 63 ... 64 // (Eighth rule) 65 retVal = currentSnapshot.test; 66 67 // (Ninth rule) 68 continue; 69 break; 70 } 71 } 72 // (Second rule) 73 return retVal; 74 }

?第十步

為了模擬下一次遞歸函數的調用，你必須在當前循環函數里面再生成一個新的“Snapshot”結構體作為下一次調用的快照，初始化其參數以后壓入棧，并“continue”。如果當前調用在執行完成后還有一些事情需要處理，那么更改它的階段狀態“stage”到相應的過程，并在new?Snapshot壓入之前，把本次的“Snapshot”壓入。

1 // Recursive Function "Tenth rule" example2 int SomeFunc(int n, int &retIdx)3 {4 ...5 if(n>0)6 {7 int test = SomeFunc(n-1, retIdx);8 test--;9 ... 10 return test; 11 } 12 ... 13 return 0; 14 } 15 16 // Conversion to Iterative Function 17 int SomeFuncLoop(int n, int &retIdx) 18 { 19 // (First rule) 20 struct SnapShotStruct { 21 int n; // - parameter input 22 int test; // - local variable that will be used 23 // after returning from the function call 24 // - retIdx can be ignored since it is a reference. 25 int stage; // - Since there is process needed to be done 26 // after recursive call. (Sixth rule) 27 }; 28 // (Second rule) 29 int retVal = 0; // initialize with default returning value 30 // (Third rule) 31 stack<SnapShotStruct> snapshotStack; 32 // (Fourth rule) 33 SnapShotStruct currentSnapshot; 34 currentSnapshot.n= n; // set the value as parameter value 35 currentSnapshot.test=0; // set the value as default value 36 currentSnapshot.stage=0; // set the value as initial stage 37 snapshotStack.push(currentSnapshot); 38 // (Fifth rule) 39 while(!snapshotStack.empty()) 40 { 41 currentSnapshot=snapshotStack.top(); 42 snapshotStack.pop(); 43 // (Sixth rule) 44 switch( currentSnapshot.stage) 45 { 46 case 0: 47 // (Seventh rule) 48 if( currentSnapshot.n>0 ) 49 { 50 // (Tenth rule) 51 currentSnapshot.stage = 1; // - current snapshot need to process after 52 // returning from the recursive call 53 snapshotStack.push(currentSnapshot); // - this MUST pushed into stack before 54 // new snapshot! 55 // Create a new snapshot for calling itself 56 SnapShotStruct newSnapshot; 57 newSnapshot.n= currentSnapshot.n-1; // - give parameter as parameter given 58 // when calling itself 59 // ( SomeFunc(n-1, retIdx) ) 60 newSnapshot.test=0; // - set the value as initial value 61 newSnapshot.stage=0; // - since it will start from the 62 // beginning of the function, 63 // give the initial stage 64 snapshotStack.push(newSnapshot); 65 continue; 66 } 67 ... 68 // (Eighth rule) 69 retVal = 0 ; 70 71 // (Ninth rule) 72 continue; 73 break; 74 case 1: 75 // (Seventh rule) 76 currentSnapshot.test = retVal; 77 currentSnapshot.test--; 78 ... 79 // (Eighth rule) 80 retVal = currentSnapshot.test; 81 // (Ninth rule) 82 continue; 83 break; 84 } 85 } 86 // (Second rule) 87 return retVal; 88 }

?

5 替代過程的幾個簡單例子

以下幾個例子均在vs2008環境下開發，主要包含了：

（1）線性遞歸

1 #ifndef __LINEAR_RECURSION_H__2 #define __LINEAR_RECURSION_H__3 4 #include <stack>5 using namespace std;6 7 /**8 * \brief 求n的階乘9 * \para 10 * \return 11 * \note result = n! 遞歸實現12 */13 int Fact(long n)14 {15 if(0>n)16 return -1;17 if(0 == n)18 return 1;19 else20 {21 return ( n* Fact(n-1));22 }23 } 24 25 /**26 * \brief 求n的階乘27 * \para 28 * \return 29 * \note result = n! 循環實現30 */31 int FactLoop(long n)32 {33 // (步驟1)34 struct SnapShotStruct // 快照結構體局部聲明 35 {36 long inputN; // 會改變的參數37 // 沒有局部變量38 int stage; // 階段變量用于快照跟蹤39 } ;40 41 // (步驟2)42 int returnVal; // 用于保存當前調用返回值 43 44 // (步驟3)45 stack<SnapShotStruct> snapshotStack;46 47 // (步驟4)48 SnapShotStruct currentSnapshot;49 currentSnapshot.inputN=n;50 currentSnapshot.stage=0; // 階段變量初始化51 52 snapshotStack.push(currentSnapshot); 53 54 // (步驟5)55 while(!snapshotStack.empty()) 56 { 57 currentSnapshot=snapshotStack.top(); 58 snapshotStack.pop(); 59 60 // (步驟6)61 switch(currentSnapshot.stage)62 {63 // (步驟7)64 case 0:65 if(0>currentSnapshot.inputN)66 {67 // (步驟8 & 步驟9)68 returnVal = -1;69 continue;70 }71 if(0 == currentSnapshot.inputN)72 {73 // (步驟8 & 步驟9)74 returnVal = 1; 75 continue;76 }77 else78 {79 // (步驟10)80 81 // 返回 ( n* Fact(n-1)); 分為2步： 82 // (第一步調用自身，第二步用返回值乘以當前n值)83 // 這里我們拍下快照.84 currentSnapshot.stage=1; // 當前的快照表示正在被處理，并等待自身調用結果返回，所以賦值為1 85 86 snapshotStack.push(currentSnapshot);87 88 // 創建一個新的快照，用于調用自身89 SnapShotStruct newSnapshot;90 newSnapshot.inputN= currentSnapshot.inputN -1 ; // 初始化參數 91 92 newSnapshot.stage = 0 ; // 從頭開始執行自身，所以賦值stage==0 93 94 snapshotStack.push(newSnapshot);95 continue;96 97 }98 break;99 // (步驟7) 100 case 1: 101 102 // (步驟8) 103 104 returnVal = currentSnapshot.inputN * returnVal; 105 106 // (步驟9) 107 continue; 108 break; 109 } 110 } 111 112 // (步驟2) 113 return returnVal; 114 } 115 #endif //__LINEAR_RECURSION_H__

（2）二分遞歸

1 #ifndef __BINARY_RECURSION_H__2 #define __BINARY_RECURSION_H__3 4 #include <stack>5 using namespace std;6 7 /**8 * \function FibNum9 * \brief 求斐波納契數列10 * \para 11 * \return 12 * \note 遞歸實現13 */14 int FibNum(int n)15 {16 if (n < 1)17 return -1;18 if (1 == n || 2 == n)19 return 1;20 21 // 這里可以看成是22 //int addVal = FibNum( n - 1);23 // addVal += FibNum(n - 2);24 // return addVal;25 return FibNum(n - 1) + FibNum(n - 2); 26 } 27 /**28 * \function FibNumLoop29 * \brief 求斐波納契數列30 * \para 31 * \return 32 * \note 循環實現33 */34 int FibNumLoop(int n)35 {36 // (步驟1)37 struct SnapShotStruct // 快照結構體局部聲明 38 {39 int inputN; // 會改變的參數40 int addVal; // 局部變量41 int stage; // 階段變量用于快照跟蹤42 43 };44 45 // (步驟2)46 int returnVal; // 用于保存當前調用返回值47 48 // (步驟3)49 stack<SnapShotStruct> snapshotStack;50 51 // (步驟4)52 SnapShotStruct currentSnapshot;53 currentSnapshot.inputN=n;54 currentSnapshot.stage=0; // 階段變量初始化55 56 snapshotStack.push(currentSnapshot);57 58 // (步驟5)59 while(!snapshotStack.empty())60 {61 currentSnapshot=snapshotStack.top();62 snapshotStack.pop();63 64 // (步驟6)65 switch(currentSnapshot.stage)66 {67 // (步驟7)68 case 0:69 if(currentSnapshot.inputN<1)70 {71 // (步驟8 & 步驟9)72 returnVal = -1;73 continue;74 }75 if(currentSnapshot.inputN == 1 || currentSnapshot.inputN == 2 )76 {77 // (步驟8 & 步驟9)78 returnVal = 1;79 continue;80 }81 else82 {83 // (步驟10)84 85 // 返回 ( FibNum(n - 1) + FibNum(n - 2)); 相當于兩步86 // (第一次調用參數是 n-1, 第二次調用參數 n-2)87 // 這里我們拍下快照，分成2個階段88 currentSnapshot.stage=1; // 當前的快照表示正在被處理，并等待自身調用結果返回，所以賦值為1 89 90 snapshotStack.push(currentSnapshot);91 92 // 創建一個新的快照，用于調用自身93 SnapShotStruct newSnapshot;94 newSnapshot.inputN= currentSnapshot.inputN -1 ; //初始化參數 FibNum(n - 1)95 96 newSnapshot.stage = 0 ; 97 snapshotStack.push(newSnapshot);98 continue;99 100 } 101 break; 102 // (步驟7) 103 case 1: 104 105 // (步驟10) 106 107 currentSnapshot.addVal = returnVal; 108 currentSnapshot.stage=2; // 當前的快照正在被處理，并等待的自身調用結果，所以階段變量變成2 109 110 snapshotStack.push(currentSnapshot); 111 112 // 創建一個新的快照，用于調用自身 113 SnapShotStruct newSnapshot; 114 newSnapshot.inputN= currentSnapshot.inputN - 2 ; // 初始化參數 FibNum(n - 2) 115 newSnapshot.stage = 0 ; // 從頭開始執行，階段變量賦值為0 116 117 snapshotStack.push(newSnapshot); 118 continue; 119 break; 120 case 2: 121 // (步驟8) 122 returnVal = currentSnapshot.addVal + returnVal; // actual addition of ( FibNum(n - 1) + FibNum(n - 2) ) 123 124 // (步驟9) 125 continue; 126 break; 127 } 128 } 129 130 // (步驟2) 131 return returnVal; 132 } 133 134 135 #endif //__BINARY_RECURSION_H__

（3）尾遞歸

1 #ifndef __TAIL_RECURSION_H__2 #define __TAIL_RECURSION_H__3 4 #include <stack>5 using namespace std;6 7 /**8 * \function FibNum29 * \brief 2階裴波那契序列 10 * \para 11 * \return 12 * \note 遞歸實現 f0 = x, f1 = y, fn=fn-1+fn-2, n=k,k+1,... 13 */ 14 int FibNum2(int n, int x, int y) 15 { 16 if (1 == n) 17 { 18 return y; 19 } 20 else 21 { 22 return FibNum2(n-1, y, x+y); 23 } 24 } 25 /** 26 * \function FibNum2Loop 27 * \brief 2階裴波那契序列 28 * \para 29 * \return 30 * \note 循環實現 在尾遞歸中, 遞歸調用后除了返回沒有任何其它的操作, 所以在變為循環時，不需要stage變量 31 */ 32 int FibNum2Loop(int n, int x, int y) 33 { 34 // (步驟1) 35 struct SnapShotStruct 36 { 37 int inputN; // 會改變的參數 38 int inputX; // 會改變的參數 39 int inputY; // 會改變的參數 40 // 沒有局部變量 41 }; 42 43 // (步驟2) 44 int returnVal; 45 46 // (步驟3) 47 stack<SnapShotStruct> snapshotStack; 48 49 // (步驟4) 50 SnapShotStruct currentSnapshot; 51 currentSnapshot.inputN = n; 52 currentSnapshot.inputX = x; 53 currentSnapshot.inputY = y; 54 55 snapshotStack.push(currentSnapshot); 56 57 // (步驟5) 58 while(!snapshotStack.empty()) 59 { 60 currentSnapshot=snapshotStack.top(); 61 snapshotStack.pop(); 62 63 if(currentSnapshot.inputN == 1) 64 { 65 // (步驟8 & 步驟9) 66 returnVal = currentSnapshot.inputY; 67 continue; 68 } 69 else 70 { 71 // (步驟10) 72 73 // 創建新快照 74 SnapShotStruct newSnapshot; 75 newSnapshot.inputN= currentSnapshot.inputN -1 ; // 初始化，調用( FibNum(n-1, y, x+y) ) 76 newSnapshot.inputX= currentSnapshot.inputY; 77 newSnapshot.inputY= currentSnapshot.inputX + currentSnapshot.inputY; 78 snapshotStack.push(newSnapshot); 79 continue; 80 } 81 } 82 // (步驟2) 83 return returnVal; 84 } 85 86 #endif //__TAIL_RECURSION_H__

（4）互遞歸

1 #ifndef __MUTUAL_RECURSION_H__2 #define __MUTUAL_RECURSION_H__3 #include <stack>4 using namespace std;5 6 bool IsEvenNumber(int n);//判斷是否是偶數7 bool IsOddNumber(int n);//判斷是否是奇數8 bool isOddOrEven(int n, int stage);//判斷是否是奇數或偶數9 10 /****************************************************/11 //互相調用的遞歸實現12 bool IsOddNumber(int n)13 {14 // 終止條件15 if (0 == n)16 return false;17 else18 // 互相調用函數的遞歸調用19 return IsEvenNumber(n - 1);20 }21 22 bool IsEvenNumber(int n)23 {24 // 終止條件25 if (0 == n)26 return true;27 else28 // 互相調用函數的遞歸調用29 return IsOddNumber(n - 1);30 } 31 32 33 /*************************************************/34 //互相調用的循環實現35 bool IsOddNumberLoop(int n)36 {37 return isOddOrEven(n , 0);38 }39 40 bool IsEvenNumberLoop(int n)41 {42 return isOddOrEven(n , 1);43 }44 45 bool isOddOrEven(int n, int stage)46 {47 // (步驟1)48 struct SnapShotStruct49 {50 int inputN; // 會改變的參數51 int stage;52 // 沒有局部變量53 };54 55 // (步驟2)56 bool returnVal; 57 58 // (步驟3)59 stack<SnapShotStruct> snapshotStack;60 61 // (步驟4)62 SnapShotStruct currentSnapshot;63 currentSnapshot.inputN = n;64 currentSnapshot.stage = stage;65 66 snapshotStack.push(currentSnapshot);67 68 // (步驟5)69 while(!snapshotStack.empty())70 {71 currentSnapshot=snapshotStack.top();72 snapshotStack.pop();73 74 // (步驟6)75 switch(currentSnapshot.stage)76 {77 // (步驟7)78 // bool IsOddNumber(int n)79 case 0:80 // 終止條件81 if (0 == currentSnapshot.inputN)82 {83 // (步驟8 & 步驟9)84 returnVal = false;85 continue;86 }87 else88 {89 // (步驟10)90 91 // 模擬互調用的遞歸調用92 93 // 創建新的快照94 SnapShotStruct newSnapshot;95 newSnapshot.inputN= currentSnapshot.inputN - 1; // 初始化參數 96 // 調用 ( IsEvenNumber(n - 1) )97 newSnapshot.stage= 1;98 snapshotStack.push(newSnapshot);99 continue; 100 } 101 102 break; 103 // (步驟7) 104 // bool IsEvenNumber(int n) 105 case 1: 106 // 終止條件 107 if (0 == currentSnapshot.inputN) 108 { 109 // (步驟8 & 步驟9) 110 returnVal = true; 111 continue; 112 } 113 else 114 { 115 // (步驟10) 116 117 // 模擬互調用的遞歸調用 118 119 // 創建新的快照 120 SnapShotStruct newSnapshot; 121 newSnapshot.inputN= currentSnapshot.inputN - 1; // 122 // calling itself ( IsEvenNumber(n - 1) ) 123 newSnapshot.stage= 0; 124 snapshotStack.push(newSnapshot); 125 continue; 126 } 127 break; 128 } 129 130 } 131 // (步驟2) 132 return returnVal; 133 } 134 135 #endif //__MUTUAL_RECURSION_H__

（5）嵌套遞歸

1 #ifndef __NESTED_RECURSION_H__2 #define __NESTED_RECURSION_H__3 #include <stack>4 using namespace std;5 6 int Ackermann(int x, int y)7 {8 // 終止條件9 if (0 == x)10 {11 return y + 1;12 } 13 // 錯誤處理條件14 if (x < 0 || y < 0)15 {16 return -1;17 } 18 // 線性方法的遞歸調用 19 else if (x > 0 && 0 == y) 20 {21 return Ackermann(x-1, 1);22 }23 // 嵌套方法的遞歸調用24 else25 {26 //可以看成是：27 // int midVal = Ackermann(x, y-1);28 // return Ackermann(x-1, midVal);29 return Ackermann(x-1, Ackermann(x, y-1));30 }31 }32 33 34 35 int AckermannLoop(int x, int y)36 {37 // (步驟1)38 struct SnapShotStruct 39 {40 int inputX; // 會改變的參數41 int inputY; // 會改變的參數42 int stage;43 // 沒有局部變量44 };45 46 // (步驟2)47 int returnVal; 48 49 // (步驟3)50 stack<SnapShotStruct> snapshotStack;51 52 // (步驟4)53 SnapShotStruct currentSnapshot;54 currentSnapshot.inputX = x;55 currentSnapshot.inputY = y;56 currentSnapshot.stage = 0;57 58 snapshotStack.push(currentSnapshot);59 60 // (步驟5)61 while(!snapshotStack.empty())62 {63 currentSnapshot=snapshotStack.top();64 snapshotStack.pop();65 66 // (步驟6)67 switch(currentSnapshot.stage)68 {69 // (步驟7)70 case 0:71 // 終止條件72 if(currentSnapshot.inputX == 0)73 {74 // (步驟8 & 步驟9)75 returnVal = currentSnapshot.inputY + 1;76 continue; // 這里必須返回77 }78 // 錯誤處理條件 79 if (currentSnapshot.inputX < 0 || currentSnapshot.inputY < 0)80 {81 // (步驟8 & 步驟9)82 returnVal = -1;83 continue; // 這里必須返回84 } 85 // 線性方法的遞歸調用 86 else if (currentSnapshot.inputX > 0 && 0 == currentSnapshot.inputY) 87 {88 // (步驟10)89 90 // 創建新快照91 SnapShotStruct newSnapshot;92 newSnapshot.inputX= currentSnapshot.inputX - 1; // 參數設定 calling itself ( Ackermann(x-1, 1) )93 newSnapshot.inputY= 1; // 參數設定 calling itself ( Ackermann(x-1, 1) )94 newSnapshot.stage= 0;95 snapshotStack.push(newSnapshot);96 continue;97 }98 // Recursive call by Nested method99 else 100 { 101 // (步驟10) 102 103 currentSnapshot.stage=1; 104 snapshotStack.push(currentSnapshot); 105 106 // 創建新快照 107 SnapShotStruct newSnapshot; 108 newSnapshot.inputX= currentSnapshot.inputX; //參數設定calling itself ( Ackermann(x, y-1) ) 109 newSnapshot.inputY= currentSnapshot.inputY - 1; //參數設定calling itself ( Ackermann(x, y-1) ) 110 newSnapshot.stage = 0; 111 snapshotStack.push(newSnapshot); 112 continue; 113 } 114 break; 115 case 1: 116 // (步驟10) 117 118 // 創建新快照 119 SnapShotStruct newSnapshot; 120 newSnapshot.inputX= currentSnapshot.inputX - 1; // 設定參數calling itself ( Ackermann(x-1, Ackermann(x, y-1)) ) 121 newSnapshot.inputY= returnVal; // 設定參數calling itself ( Ackermann(x-1, Ackermann(x, y-1)) ) 122 newSnapshot.stage = 0; 123 snapshotStack.push(newSnapshot); 124 continue; 125 break; 126 } 127 } 128 // (步驟2) 129 return returnVal; 130 } 131 #endif //__NESTED_RECURSION_H__

測試代碼：

1 #include <tchar.h>2 #include "BinaryRecursion.h"3 #include "LinearRecursion.h"4 #include "MutualRecursion.h"5 #include "NestedRecursion.h"6 #include "TailRecursion.h"7 8 9 int _tmain(int argc,_TCHAR argv[] ) 10 { 11 // Binary Recursion 12 int result = FibNum(10); 13 int result2 = FibNumLoop(10); 14 15 printf("FibNum(10) = %d\n",result); 16 printf("FibNumLoop(10) = %d\n",result2); 17 18 19 // Linear Recursion 20 result = Fact(10); 21 result2 = FactLoop(10); 22 23 printf("Fact(10) = %d\n",result); 24 printf("FactLoop(10) = %d\n",result2); 25 26 27 // Tail Recursion 28 result = FibNum2(10,5,4); 29 result2 = FibNum2Loop(10,5,4); 30 31 printf("FibNum2(10,5,4) = %d\n",result); 32 printf("FibNumLoop2(10,5,4) = %d\n",result2); 33 34 35 // Mutual Recursion 36 bool bResult = IsOddNumber(10); 37 bool bResult2 = IsOddNumberLoop(10); 38 39 bool bResult3 = IsEvenNumber(10); 40 bool bResult4 = IsEvenNumberLoop(10); 41 42 printf("IsOddNumber(10) = %d\n",(int)bResult); 43 printf("IsOddNumberLoop(10) = %d\n",(int)bResult2); 44 printf("IsEvenNumber(10) = %d\n",(int)bResult3); 45 printf("IsEvenNumberLoop(10) = %d\n",(int)bResult4); 46 47 48 // Nested Recursion 49 result = Ackermann(3,2); 50 result2 = AckermannLoop(3,2); 51 52 printf("Ackermann(3,2) = %d\n",result); 53 printf("AckermannLoop(3,2) = %d\n",result2); 54 55 while(1){} 56 return 0; 57 }

?

6 更多的例子

• epQuickSort.h
• epMergeSort.h
• epKAryHeap.h
• epPatriciaTree.h

7 結論

我的結論就是在c/c++或者Java代碼中，盡量避免用遞歸。但是正如你看到的，遞歸容易理解，但是容易導致棧溢出。雖然循環版本的函數不會增加代碼可讀性和提升性能，但是它能有效的避免沖突或未定義行為。正如我開頭所說，我的做法通常是在代碼中寫兩份代碼，一份遞歸，一份循環的。前者用于理解代碼，后者用于實際的運行和測試用。如果你對于自己代碼中使用這兩種代碼的利弊很清楚，你可以選擇你自己的方式。

8 參考

• http://www.dreamincode.net/forums/topic/51296-types-of-recursion/
• EpLibrary 2.0

9 License

本文及包含的代碼遵從協議?The MIT License

?

?

?************************************************************************************************************

原文：http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

以上就是原文的一些內容，感謝原作者Woong Gyu La。

這篇文章中的代碼我在調式過程中，發現了一個問題：循環版本的函數在執行效率方面存在問題。以后再改

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的如何利用循环代替递归以防止栈溢出(译)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。