Table of contents
 Introduction
 Purpose of Simulated function
 Pros and cons of Recursive and Simulated functions
 10 rules (steps) for replacing the recursive function using stack and whileloop
 First rule
 Second rule
 Third rule
 Fourth rule
 Fifth rule
 Sixth rule
 Seventh rule
 Eighth rule
 Ninth rule
 Tenth rule
 Simple examples by types of recursion
 More practical example sources
 Why do the sources contain both the simulated version and the recursive version?
 Conclusion
 Reference
Introduction
There are cases where we prefer to use recursive functions such as sort (Merge Sort) or tree operations (heapify up / heapify down). However, if the recursive function goes too deep in some environments, such as in Visual C++ code, an unwanted result might occur such as a stackoverflow. Many professional developers probably already know how to replace recursive functions to avoid stackoverflow problems in advance by replacing with iterative function or using stack (heap stack) and whileloop (recursive simulation function). However I thought it would be a great idea to share simple and general methods (or guidelines) to replace the recursive functions using stack (heap stack) and whileloop to avoid the stackoverflow to help novice developers.
Purpose of the Simulated function
If you are using recursive function, since you don't have control on call stack and the stack is limited, the stackoverflow/heapcorruption might occur when the recursive call's depth gets too deep. The purpose of simulated function is moving the call stack to stack in heap, so the you can have more control on memory and process flow, and avoid the stackoverflow. It will be much better if it is replaced by iterative function, however in order to do that, it takes time and experience to handle every recursive function in proper way, so this article is a simple guide to help the novice developers to avoid the stackoverflow by using the recursive function, when they are not ready yet to handle everything in proper way.
Pros and Cons of Recursive and Simulated function
Recursive function
 Pros
 Very intuitive about the algorithm
 Cons
 May occur "Stackoverflow," or "Heap corruption"
 Try to run
IsEvenNumber
function (Recursive) and IsEvenNumberLoop
function (simulated) of "MutualRecursion.h" in RecursiveToLoopSamples.zip with "10000" as its parameter input.
#include "MutualRecursion.h"
bool result = IsEvenNumberLoop(10000); bool result2 = IsEvenNumber(10000);
Some people say that "(In order to fix the stackoverflow occurred by recursive function,) increase the MAX value of the stack to avoid the stackoverflow." However this is just temporary bandage, since if the recursive call gets deeper and deeper, the stackoverflow will most likely reappear.
Simulated function
 Pros
 Can avoid "Stackoverflow," or "Heap corruption" errors.
 More control on process flow and memory.
 Cons
 Not very intuitive about the algorithm.
 Hard to maintain the code.
10 Rules (steps) for replacing the recursive function with stack and whileloop
First rule
 Define a new struct called "
Snapshot
". The purpose of this data structure is to hold any data used in the recursive structure, along with any state information.
 Things to include in the "
Snapshot
" structure.
 the function argument that changes when the recursive function calls itself **However,** when the function argument is a reference, it does not need to be included in the
Snapshot
struct. Thus, in the following example, argument n
should be included in the struct but argument retVal
should not.
void SomeFunc(int n, int &retVal);
 the "
Stage
" variable (usually an int
to switch into the correct process divisions)
 Read "Sixth rule" for detail.
 local variables that will be used after returning from the function call (can happen during binary recursion or nested recursion)
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
...
}
Second rule
 Create a local variable at the top of the function. This value will represent the role of the return function in the recursive function.
 in the iterative function, it is more like a temporary return value holder for each recursive call within the recursive function, since a C++ function can only have one return type.
 if the recursive function's return type is
void
, then you can simply ignore creating this variable.
 If there is any default return value then initialize this local variable with default value returning.
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0;
...
return retVal;
}
Third rule
 Make a stack with the "
Snapshot
" struct type.
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0;
stack<SnapShotStruct> snapshotStack;
...
return retVal;
}
Fourth rule
 Create a new "
Snapshot
" instance, and initialize with parameters that are input into the iterative function and the start "Stage
" number.
 Push the
Snapshot
instance into the empty stack.
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0;
stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0;
snapshotStack.push(currentSnapshot);
...
return retVal;
}
Fifth rule
 Make a
while
loop which continues to loop while the stack is not empty.
 At each iteration of the
while
loop, pop a Snapshot
object from the stack
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0; stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0; snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
...
}
return retVal;
}
Sixth rule
 Split the stages into two (for the case where there is only a single recursive call in the recursive function). The first case represents the code in the recursive function that is processed before the next recursive call is made, and the second case represents the code that is processed when the next recursive call returns (and when a return value is possibly collected or accumulated before the function returns it).
 In the situation where there are two recursive calls within a function, there must be three stages:
 ** (Stage 1 > recursive call > (returned from first recursive call) Stage 2 (recursive call within stage 1)> (return from second recursive call) Stage 3
 In the situation where there are three different recursive calls then there must be at least 4 stages.
 And so on.
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0; stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0; snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
switch( currentSnapshot.stage)
{
case 0:
... break;
case 1:
... break;
}
}
return retVal;
}
Seventh rule
 Switch into the process division according to the " Stage " variable
 Do the relevant process
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0;
stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0;
snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
switch( currentSnapshot.stage)
{
case 0:
if( currentSnapshot.n>0 )
{
...
}
...
break;
case 1:
currentSnapshot.test = retVal;
currentSnapshot.test;
...
break;
}
}
return retVal;
}
Eighth rule
 If there is a return type for the recursive function, store the result of the loop iteration in a local variable (such as retVal ).
 This local variable will contain the final result of the recursive function when the
while
loop exits.
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0; stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0; snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
switch( currentSnapshot.stage)
{
case 0:
if( currentSnapshot.n>0 )
{
...
}
...
retVal = 0 ;
...
break;
case 1:
currentSnapshot.test = retVal;
currentSnapshot.test;
...
retVal = currentSnapshot.test;
...
break;
}
}
return retVal;
}
Ninth rule
 In a case where there are "
return
" keywords within the recursive function, the "return
" keywords should be converted to "continue
" within the "while
" loop.

 In a case where the recursive function returns a value, then as stated in "Eighth rule," store the return value in the local variable (such as
retVal
), and then "continue
"
 Most of the time, "Ninth rule" is optional, but it helps avoid logic error.
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0; stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0; snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
switch( currentSnapshot.stage)
{
case 0:
if( currentSnapshot.n>0 )
{
...
}
...
retVal = 0 ;
continue;
break;
case 1:
currentSnapshot.test = retVal;
currentSnapshot.test;
...
retVal = currentSnapshot.test;
continue;
break;
}
}
return retVal;
}
Tenth rule (and the last...)
 To convert the recursive call within the recursive function, in iterative function, make a new "Snapshot" object, initialize the new "
Snapshot
" object stage, set its member variables according to recursive call parameters, and push into the stack, and "continue
"
 If there is process to be done after the recursive call, change the stage variable of current "Snapshot" object to the relevant stage, and push into the stack before pushing the new "Snapshot" object into the stack.
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n1, retIdx);
test;
...
return test;
}
...
return 0;
}
int SomeFuncLoop(int n, int &retIdx)
{
struct SnapShotStruct {
int n; int test; int stage; };
int retVal = 0; stack<SnapShotStruct> snapshotStack;
SnapShotStruct currentSnapshot;
currentSnapshot.n= n; currentSnapshot.test=0; currentSnapshot.stage=0; snapshotStack.push(currentSnapshot);
while(!snapshotStack.empty())
{
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
switch( currentSnapshot.stage)
{
case 0:
if( currentSnapshot.n>0 )
{
currentSnapshot.stage = 1; snapshotStack.push(currentSnapshot); SnapShotStruct newSnapshot;
newSnapshot.n= currentSnapshot.n1; newSnapshot.test=0; newSnapshot.stage=0; snapshotStack.push(newSnapshot);
continue;
}
...
retVal = 0 ;
continue;
break;
case 1:
currentSnapshot.test = retVal;
currentSnapshot.test;
...
retVal = currentSnapshot.test;
continue;
break;
}
}
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.
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 stackoverflow 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 stackoverflow 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
History
 07.02.2015: Broken link fixed
 09.06.2013: Typo fixed (Thanks to lovewubo)
 08.22.2013: Redistributed 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 reorganized.
 Ninth and Tenth rule added.
 Examples for each rule added.
 07.11.2012:  Submitted the article.