10 Rules (steps) for replacing the recursive function with stack and while-loop

轉自http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and??

First rule

定義一個新的數據結構"Snapshot".他的作用是保存隊規過程中的中間值數據和狀態信息。

?"Snapshot" 結構中包含：

遞歸函數的參數，但是，如果遞歸函數的參數是引用類型的參數，則無需放到Snapshot?中. 因此, 實例如下, 參數n?應該放在Snapshot?中，而引用類型的參數?retVal?不放Snapshot?中.

• void SomeFunc(int n, int &retVal);

遞歸的條件分類值 "Stage"? (通常是一個int?值，可以放在 switch語句中，分別處理不同的情況)

• 細節參照第六條sixth rule.

存儲函數返回值的局部變量

? // Recursive Function "First rule" example int SomeFunc(int n, int &retIdx) {...if(n>0){int test = SomeFunc(n-1, retIdx);test--;...return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) { // (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call// - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; ... }

Second rule

在函數頂層創建一個局部變量，用于存儲最終結果（遞歸函數的返回值retVal = currentSnapshot.test）。

在迭代過程中,它象一個臨時變量保存每一次遞歸調用的返回值.

如果遞歸函數返回類型是空void, 忽略此步.

如果有默認的返回值，用默認值初始化這個局部變量。

? // Recursive Function "Second rule" example int SomeFunc(int n, int &retIdx) {...if(n>0) { int test = SomeFunc(n-1, retIdx); test--; ... return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) {// (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference.// (Second rule返回值retVal = currentSnapshot.test)
int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value ... // (Second rule) return retVal; }

Third rule

建一個"Snapshot" 類型的堆棧.

? // Recursive Function "Third rule" example// Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) { // (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; ... // (Second rule) return retVal; }

Fourth rule

創建 "Snapshot" 實例,并初始化輸入到迭代中的參數和遞歸條件分類的初始值"Stage" .

把Snapshot實例壓棧stack.

? // Recursive Function "Fourth rule" example// Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) { // (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); ... // (Second rule) return retVal; }

Fifth rule

建一個?while循環，當 堆棧stack 不空時執行循環。

在while?循環的每次迭代中, pop?出棧一個?Snapshot?對象；

? // Recursive Function "Fifth rule" example// Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) { // (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); // (Fifth rule) while(!snapshotStack.empty()) { currentSnapshot=snapshotStack.top(); snapshotStack.pop(); ... } // (Second rule) return retVal; }

Sixth rule遞歸條件分類處理

分2步處理 stages 。第一步對在當前遞歸函數調用之前的處理，第二步是在當前遞歸函數調用之后對返回值進行一些運算。

如果遞歸過程要調用2個函數, 就要對stages分3步處理:

** (Stage 1 --> recursive call --> (returned from first recursive call) Stage 2 (recursive call within stage 1)--> (return from second recursive call) Stage 3

如果有3個不同的遞歸調用，至少分4步驟處理 stages.

以此類推.

? // Recursive Function "Sixth rule" example int SomeFunc(int n, int &retIdx) {...if(n>0) { int test = SomeFunc(n-1, retIdx); test--; ... return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) {// (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); // (Fifth rule) while(!snapshotStack.empty()) { currentSnapshot=snapshotStack.top(); snapshotStack.pop(); // (Sixth rule) switch( currentSnapshot.stage) { case 0: ... // before ( SomeFunc(n-1, retIdx); ) break; case 1: ... // after ( SomeFunc(n-1, retIdx); ) break; } } // (Second rule) return retVal; }

Seventh rule

根據不同的Switch 處理不同的Stage?

做相關的處理

? // Recursive Function "Seventh rule" example int SomeFunc(int n, int &retIdx) {... if(n>0) {int test = SomeFunc(n-1, retIdx); test--; ... return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) {// (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); // (Fifth rule) while(!snapshotStack.empty()) { currentSnapshot=snapshotStack.top(); snapshotStack.pop(); // (Sixth rule) switch( currentSnapshot.stage) { case 0: // (Seventh rule) if( currentSnapshot.n>0 ) { ... } ... break; case 1: // (Seventh rule) currentSnapshot.test = retVal; currentSnapshot.test--; ... break; } } // (Second rule) return retVal; }

Eighth rule

如果遞歸函數有返回值，在每次循環迭代時，保存返回值到局部變量 (如 retVal?).

這個局部變量retVal?就是循環結束后，遞歸的最終值.

? // Recursive Function "Eighth rule" example int SomeFunc(int n, int &retIdx) {...if(n>0) { int test = SomeFunc(n-1, retIdx); test--; ... return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) {// (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); // (Fifth rule) while(!snapshotStack.empty()) { currentSnapshot=snapshotStack.top(); snapshotStack.pop(); // (Sixth rule) switch( currentSnapshot.stage) { case 0: // (Seventh rule) if( currentSnapshot.n>0 ) { ... } ... // (Eighth rule) retVal = 0 ; ... break; case 1: // (Seventh rule) currentSnapshot.test = retVal; currentSnapshot.test--; ... // (Eighth rule) retVal = currentSnapshot.test; ... break; } } // (Second rule) return retVal; }

Ninth rule

如果遞歸含有返回值，把原來遞歸函數中的關鍵字 "return" 替換成"while"循環中的關鍵字 "continue"。

• 如果遞歸函數有返回值，如 "Eighth rule,"所述，把返回值保存到局部變量中 (如?retVal), 然后"continue"繼續循環；
• 多數情況下, "Ninth rule" 是可選的,但他有助于避免邏輯錯誤.

? // Recursive Function "Ninth rule" example int SomeFunc(int n, int &retIdx) {...if(n>0) { int test = SomeFunc(n-1, retIdx); test--; ... return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) {// (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); // (Fifth rule) while(!snapshotStack.empty()) { currentSnapshot=snapshotStack.top(); snapshotStack.pop(); // (Sixth rule) switch( currentSnapshot.stage) { case 0: // (Seventh rule) if( currentSnapshot.n>0 ) { ... } ... // (Eighth rule) retVal = 0 ; // (Ninth rule) continue; break; case 1: // (Seventh rule) currentSnapshot.test = retVal; currentSnapshot.test--; ... // (Eighth rule) retVal = currentSnapshot.test; // (Ninth rule) continue; break; } } // (Second rule) return retVal; }

Tenth rule (and the last...)

為了實現從遞歸調用到迭代函數的轉換,在每次迭代中，創建一個新的? "Snapshot" 對象, 初始化 這個新的"Snapshot" 對象和遞歸條件分類 stage, 依據遞歸函數的參數設置他的成員變量，壓棧, 然后繼續 "continue"

如果遞歸函數調用之后，有其他處理過程，就需要調整當前"currentSnapshot"中保持的遞歸條件分類 stage ，并把當前"Snapshot"壓棧，然后再對新建的"Snapshot"壓棧。

? // Recursive Function "Tenth rule" example int SomeFunc(int n, int &retIdx) {...if(n>0) { int test = SomeFunc(n-1, retIdx); test--; ... return test; } ... return 0; } ? // Conversion to Iterative Function int SomeFuncLoop(int n, int &retIdx) {// (First rule) struct SnapShotStruct { int n; // - parameter input int test; // - local variable that will be used // after returning from the function call // - retIdx can be ignored since it is a reference. int stage; // - Since there is process needed to be done // after recursive call. (Sixth rule) }; // (Second rule) int retVal = 0; // initialize with default returning value // (Third rule) stack<SnapShotStruct> snapshotStack; // (Fourth rule) SnapShotStruct currentSnapshot; currentSnapshot.n= n; // set the value as parameter value currentSnapshot.test=0; // set the value as default value currentSnapshot.stage=0; // set the value as initial stage snapshotStack.push(currentSnapshot); // (Fifth rule) while(!snapshotStack.empty()) { currentSnapshot=snapshotStack.top(); snapshotStack.pop(); // (Sixth rule) switch( currentSnapshot.stage) { case 0: // (Seventh rule) if( currentSnapshot.n>0 ) { // (Tenth rule) currentSnapshot.stage = 1; // - current snapshot need to process after// returning from the recursive call snapshotStack.push(currentSnapshot); // - this MUST pushed into stack before // new snapshot! // Create a new snapshot for calling itself SnapShotStruct newSnapshot; newSnapshot.n= currentSnapshot.n-1; // - give parameter as parameter given // when calling itself // ( SomeFunc(n-1, retIdx) ) newSnapshot.test=0; // - set the value as initial value newSnapshot.stage=0; // - since it will start from the // beginning of the function, // give the initial stage snapshotStack.push(newSnapshot); continue; } ... // (Eighth rule) retVal = 0 ; // (Ninth rule) continue; break; case 1: // (Seventh rule) currentSnapshot.test = retVal; currentSnapshot.test--; ... // (Eighth rule) retVal = currentSnapshot.test; // (Ninth rule) continue; break; } } // (Second rule) return retVal; }

Simple Examples by types of recursion??

• Please download?RecursiveToLoopSamples.zip
• Unzip the file.
• Open the project with Visual Studio.
  • This project has been developed with Visual Studio 2008
• Sample project contains
  • Linear Recursion Example
  • Binary Recursion Example
  • Tail Recursion Example
  • Mutual Recursion Example
  • Nested Recursion Example

More Practical Example Sources??

The below sources contain both a recursive version and a simulated version, where the simulated version has been derived using the above methodology.?

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

Why do the sources contain both the simulated version and the recursive version???

If you look at the source, you can easily notice the simulated versions look much more complex than the recursive versions.?For those who don't know what the function does, it will be much harder to figure out what the function with the loop actually does.?So I prefer to keep both versions, so people can easily test out simple inputs and outputs with the recursive version, and for huge operations, use simulated version to avoid stack overflow.?

Conclusion???

My belief is that when writing C/C++ or Java code, the recursive functions MUST be used with care to avoid the stack-overflow error. However as you can see from the examples, in many cases, the recursive functions are easy to understand, and easy to write with the downside of "if the recursive function call's depth goes too deep, it leads to stack-overflow error". So conversion from recursive function to?simulated function is not for increasing readability nor increasing algorithmic performance, but it is simple way of evading the crashes or undefined behaviors/errors. As I stated above, I prefer to keep both recursive version and?simulated version in my code, so I can use the recursive version for readability and?maintenance of the code, and the simulated version for running and testing the code.??It will be your choice how to write your code as long as you know the pros and cons?for the choice, you are making.??

Reference???

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

History??

• 07.02.2015:- Broken link fixed
• 09.06.2013:- Typo fixed (Thanks to ?lovewubo)?
• 08.22.2013:- ?Re-distributed under MIT License from GPL v3?
• 08.10.2012: - Table of contents updated?
• 08.04.2012: - Moved the article's subsection to "Howto"?
• 07.23.2012: - Minor fixes on the article??
• 07.13.2012: - Table of contents modified?
  • Sections removed
  • Moved the article to Beginner section?
  • Changed the wording?
• 07.13.2012: - Table of contents added.
  • Titles modified.
  • New sections added.
    • Difference between Recursive and Iterative function
    • Pros and Cons of Recursive and Iterative approach
• 07.12.2012: - Sample bugs fixed.
  • Article re-organized.
  • Ninth and Tenth rule added.
  • Examples for each rule added.
• 07.11.2012: - Submitted the article.

License

This article, along with any associated source code and files, is licensed under?The MIT License

轉載于:https://www.cnblogs.com/baiyu/p/4625848.html

總結

以上是生活随笔為你收集整理的如何用堆栈和循环结构代替递归调用--递归转换为非递归的10条军规的全部內容，希望文章能夠幫你解決所遇到的問題。

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