재 귀적 호출 - 재 귀적 이 아 닌 10 개의 군 규 를 스 택 과 순환 구조 로 대체 하 는 방법

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 구문 에 넣 고 각각 다른 상황 을 처리 할 수 있 습 니 다)
세부 사항 은 제6 조 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).
교체 과정 에서, 그것 은 임시 변수 처럼 매번 귀속 호출 된 반환 값 을 저장 합 니 다. 재 귀 함수 반환 형식 이 비어 있 으 면 이 단 계 를 무시 합 니 다. 기본 반환 값 이 있 으 면 기본 값 으로 이 부분 변 수 를 초기 화 합 니 다.

 

// 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
"void" 유형의 스 택 을 만 듭 니 다.  

// 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" 인 스 턴 스 를 만 들 고 교체 에 입력 한 매개 변수 와 재 귀 조건 분류의 초기 값 "Snapshot 을 초기 화 합 니 다. Stage 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
짓다  Snapshot 스 택 stack 이 비어 있 지 않 을 때 순환 을 실행 합 니 다.
네 while ，  반복 할 때마다 pop 창고 에서 출고 하 다.  while  대상
 

// 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 귀속 조건 분류 처리
stages 를 2 단계 로 나 누 어 처리 하 다.첫 번 째 단 계 는 현재 재 귀 함수 가 호출 되 기 전에 처리 하고 두 번 째 단 계 는 현재 재 귀 함수 가 호출 된 후에 반환 값 을 연산 하 는 것 입 니 다.
재 귀 과정 에서 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
재 귀 에 반환 값 이 포함 되 어 있 으 면 원래 재 귀 함수 의 키워드 'Snapshot' 를 'return' 순환 중의 키워드 'while 로 교체 합 니 다. 재 귀 함수 에 반환 값 이 있 으 면 "Eighth rule" 과 같이 반환 값 을 부분 변수 에 저장 합 니 다 (예:  continue) 그리고 'retVal' 계속 순환 합 니 다. 대부분의 경우 '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" 대상 은 이 새로운 "continue" 대상 과 재 귀 조건 분류 stage 를 초기 화하 고 재 귀 함수 의 매개 변수 에 따라 그의 구성원 변 수 를 설정 하고 스 택 을 누 른 다음 에 계속 "Snapshot" 재 귀 함수 호출 후 다른 처리 과정 이 있 으 면 현재 "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