Click here to Skip to main content
Click here to Skip to main content
Search within:



 
Comments & Discussions (33)

How to replace recursive functions using stack and while-loop to avoid the stack-overflow

By , 9 Aug 2012
 
Prize winner in Competition "Best C++ article of July 2012"

Table of contents  

  1. Introduction 
  2. Purpose of the Simulated function 
  3. Pros and Cons of Recursive and Simulated function  
  4. 10 Rules (steps) for replacing the recursive function using stack and while-loop   
    1. First rule 
    2. Second rule 
    3. Third rule
    4. Fourth rule
    5. Fifth rule
    6. Sixth rule
    7. Seventh rule
    8. Eighth rule
    9. Ninth rule
    10. Tenth rule 
  5. Simple Examples by types of recursion 
  6. More Practical Example Sources
  7. Why do the sources contain both the simulated version and the recursive version?
  8. Conclusion
  9. 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 stack-overflow. Many professional developers probably already know how to replace recursive functions to avoid stack-overflow problems in advance by replacing with iterative function or using stack (heap stack) and while-loop (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 while-loop to avoid the stack-overflow 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 stack-overflow/heap-corruption 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 stack-overflow. 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 stack-overflow 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 
  • Cons  
    • May occur "Stack-overflow," 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); // returns successfully
bool result2 = IsEvenNumber(10000);     // stack-overflow error occurs

Some people say that "(In order to fix the stack-overflow occurred by recursive function,) increase the MAX value of the stack to avoid the stack-overflow." However this is just temporary bandage, since if the recursive call gets deeper and deeper, the stack-overflow will most likely reappear. 

Simulated function 

  • Pros 
    • Can avoid "Stack-overflow," 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 while-loop  

First rule   

  1. 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.
  2. Things to include in the "Snapshot" structure.
    1. 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);
    2. the "Stage" variable (usually an int to switch into the correct process divisions)
      • Read "Sixth rule" for detail.
    3. local variables that will be used after returning from the function call (can happen during binary recursion or nested recursion)
// 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  

  1. Create a local variable at the top of the function. This value will represent the role of the return function in the recursive function.
    1. 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.
    2. if the recursive function's return type is void, then you can simply ignore creating this variable.
    3. If there is any default return value then initialize this local variable with default value returning.
// 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.
       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   

  1. Make a stack with the "Snapshot" struct type.
// 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   

  1. Create a new "Snapshot" instance, and initialize with parameters that are input into the iterative function and the start "Stage" number.
  2. Push the Snapshot instance into the empty 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    

  1. Make a while loop which continues to loop while the stack is not empty.
  2. At each iteration of the while loop, pop a Snapshot object from the stack
// 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    

  1. 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).
  2. In the situation where there are two recursive calls within a function, there must be three stages:
    1. ** (Stage 1 --> recursive call --> (returned from first recursive call) Stage 2 (recursive call within stage 1)--> (return from second recursive call) Stage 3
  3. In the situation where there are three different recursive calls then there must be at least 4 stages.
  4. And so on.
// 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   

  1. Switch into the process division according to the " Stage " variable
  2. Do the relevant process 
// 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   

  1. If there is a return type for the recursive function, store the result of the loop iteration in a local variable (such as retVal ).
  2. This local variable will contain the final result of the recursive function when the while loop exits.
// 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 = test;
          ...
          break;
       }
    }
    // (Second rule)
    return retVal;
}

Ninth rule  

  1. In a case where there are "return" keywords within the recursive function, the  "return" keywords should be converted to "continue" within the "while" loop.
    1. 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"
    2. Most of the time, "Ninth rule" is optional, but it helps avoid logic error.
// 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 = test;

          // (Ninth rule)
          continue;
          break;
       }
    }
    // (Second rule)
    return retVal;
}

Tenth rule (and the last...)  

  1. 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"
  2. 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.
// 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 = 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. 

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 avoided in all cases. 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 helpful to avoid 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  

  • 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 Code Project Open License (CPOL)

About the Author

 Woong Gyu La
CEO P&D Soft Co.
Korea (Republic Of) Korea (Republic Of)
Member
Woong Gyu La had been working as a software developer for over 5 years.
 
His personal interests are improving his personal projects, the EpLibrary Project which is Visual C++ Utility Library, EpOraLibrary, the Oracle OCI Wrapper Library for Visual C++, and EpServerEngine, the Visual C++ WinSock Server/Client Engine.
 
If you are also intrested, you can check it out at
 
https://github.com/juhgiyo/EpLibrary[^]
 
https://github.com/juhgiyo/EpOraLibrary[^]
 
https://github.com/juhgiyo/EpServerEngine[^]

Article Top
 
Sign Up to vote   Poor Excellent
Add a reason or comment to your vote: x
Votes of 3 or less require a comment

Comments and Discussions

 
You must Sign In to use this message board.
Search this forum  
    Spacing  Noise  Layout  Per page   
First PrevNext
Questionconversion of recursive to loopmemberMember 991447115 Mar '13 - 6:25 
My recursive function call itself within a for loop located inside it. Then, how to convert that kind of recursive function to a loop? I tried your method. But, I can't understand how to convert that for loop part
Sign In·View Thread·Permalink
AnswerRe: conversion of recursive to loopmemberWoong Gyu La15 Mar '13 - 17:07 
If the recursive function call is within the for loop, then generally you can make
 
for stage0:
Operations before the recursive function call
push to the current Snapshot to the stack with changing the stage as 1 and the for-loop condition (ex. for-loop index)
push new Snapshot for recursive function call with stage0
 
for stage1:
Operations after the recursive function call return
start for-loop as stage0 with the index saved from stage0.
push to the current Snapshot to the stack with changing the stage as 1 and the for-loop condition (ex. for-loop index) if for-loop is not expired.
push new Snapshot for recursive function call with stage0.
 
Important thing is you split the stages as before the recursive function call and after the recursive function call.
But things can become complex when recursive function call happens within for-loop depends on tail-recursion, linear recursion, binary recursion etc.
Sign In·View Thread·Permalink
Questionconversion of recursive to loopmembermadhurisamudrala14 Mar '13 - 8:13 
Hello,
 
I am doing high level synthesis for my aquisition algorithm. On that I have Split Radix Fast Fourier algorithm. In that they used recursive function. But my Vivado HLS platofrom is not supporting recursive functions. Can you please help me how to convert it to loop.
here is my code
void srrec(double *xr, double *xi, int logm)
{
static int m, m2, m4, m8, nel, n;
static double *xr1, *xr2, *xi1, *xi2;
static double *cn, *spcn, *smcn, *c3n, *spc3n, *smc3n;
static double tmp1, tmp2, ang, c, s;
static double *tab[MAXLOGM];

/* Check range of logm */
if ((logm < 0) || (logm > MAXLOGM)) {
printf("Error : SRFFT : logm = %d is out of bounds [%d, %d]\n",
logm, 0, MAXLOGM);
//error_exit();
}

/* Compute trivial cases */
if (logm < 3) {
if (logm == 2) { /* length m = 4 */
xr2 = xr + 2;
xi2 = xi + 2;
tmp1 = *xr + *xr2;
*xr2 = *xr - *xr2;
*xr = tmp1;
tmp1 = *xi + *xi2;
*xi2 = *xi - *xi2;
*xi = tmp1;
xr1 = xr + 1;
xi1 = xi + 1;
xr2++;
xi2++;
tmp1 = *xr1 + *xr2;
*xr2 = *xr1 - *xr2;
*xr1 = tmp1;
tmp1 = *xi1 + *xi2;
*xi2 = *xi1 - *xi2;
*xi1 = tmp1;
xr2 = xr + 1;
xi2 = xi + 1;
tmp1 = *xr + *xr2;
*xr2 = *xr - *xr2;
*xr = tmp1;
tmp1 = *xi + *xi2;
*xi2 = *xi - *xi2;
*xi = tmp1;
xr1 = xr + 2;
xi1 = xi + 2;
xr2 = xr + 3;
xi2 = xi + 3;
tmp1 = *xr1 + *xi2;
tmp2 = *xi1 + *xr2;
*xi1 = *xi1 - *xr2;
*xr2 = *xr1 - *xi2;
*xr1 = tmp1;
*xi2 = tmp2;
return;
}
else if (logm == 1) { /* length m = 2 */
xr2 = xr + 1;
xi2 = xi + 1;
tmp1 = *xr + *xr2;
*xr2 = *xr - *xr2;
*xr = tmp1;
tmp1 = *xi + *xi2;
*xi2 = *xi - *xi2;
*xi = tmp1;
return;
}
else if (logm == 0) return; /* length m = 1 */
}

/* Compute a few constants */
m = 1 << logm; m2 = m / 2; m4 = m2 / 2; m8 = m4 /2;

/* Build tables of butterfly coefficients, if necessary */
if ((logm >= 4) && (tab[logm-4] == NULL)) {

/* Allocate memory for tables */
nel = m4 - 2;
if ((tab[logm-4] = (double *) calloc(6 * nel, sizeof(double))) == NULL) {
// error_exit();
}

/* Initialize pointers */
cn = tab[logm-4]; spcn = cn + nel; smcn = spcn + nel;
c3n = smcn + nel; spc3n = c3n + nel; smc3n = spc3n + nel;

/* Compute tables */
for (n = 1; n < m4; n++) {
if (n == m8) continue;
ang = n * TWOPI / m;
c = cos(ang); s = sin(ang);
*cn++ = c; *spcn++ = - (s + c); *smcn++ = s - c;
ang = 3 * n * TWOPI / m;
c = cos(ang); s = sin(ang);
*c3n++ = c; *spc3n++ = - (s + c); *smc3n++ = s - c;
}
}

/* Step 1 */
xr1 = xr; xr2 = xr1 + m2;
xi1 = xi; xi2 = xi1 + m2;
for (n = 0; n < m2; n++) {
tmp1 = *xr1 + *xr2;
*xr2 = *xr1 - *xr2;
*xr1 = tmp1;
tmp2 = *xi1 + *xi2;
*xi2 = *xi1 - *xi2;
*xi1 = tmp2;
xr1++; xr2++; xi1++; xi2++;
}

/* Step 2 */
xr1 = xr + m2; xr2 = xr1 + m4;
xi1 = xi + m2; xi2 = xi1 + m4;
for (n = 0; n < m4; n++) {
tmp1 = *xr1 + *xi2;
tmp2 = *xi1 + *xr2;
*xi1 = *xi1 - *xr2;
*xr2 = *xr1 - *xi2;
*xr1 = tmp1;
*xi2 = tmp2;
xr1++; xr2++; xi1++; xi2++;
}

/* Steps 3 & 4 */
xr1 = xr + m2; xr2 = xr1 + m4;
xi1 = xi + m2; xi2 = xi1 + m4;
if (logm >= 4) {
nel = m4 - 2;
cn = tab[logm-4]; spcn = cn + nel; smcn = spcn + nel;
c3n = smcn + nel; spc3n = c3n + nel; smc3n = spc3n + nel;
}
xr1++; xr2++; xi1++; xi2++;
for (n = 1; n < m4; n++) {
if (n == m8) {
tmp1 = SQHALF * (*xr1 + *xi1);
*xi1 = SQHALF * (*xi1 - *xr1);
*xr1 = tmp1;
tmp2 = SQHALF * (*xi2 - *xr2);
*xi2 = -SQHALF * (*xr2 + *xi2);
*xr2 = tmp2;
} else {
tmp2 = *cn++ * (*xr1 + *xi1);
tmp1 = *spcn++ * *xr1 + tmp2;
*xr1 = *smcn++ * *xi1 + tmp2;
*xi1 = tmp1;
tmp2 = *c3n++ * (*xr2 + *xi2);
tmp1 = *spc3n++ * *xr2 + tmp2;
*xr2 = *smc3n++ * *xi2 + tmp2;
*xi2 = tmp1;
}
xr1++; xr2++; xi1++; xi2++;
}

/* Call ssrec again with half DFT length */
srrec(xr, xi, logm-1);

/* Call ssrec again twice with one quarter DFT length.
Constants have to be recomputed, because they are static! */
m = 1 << logm; m2 = m / 2;
srrec(xr + m2, xi + m2, logm-2);
m = 1 << logm; m4 = 3 * (m / 4);
srrec(xr + m4, xi + m4, logm-2);
}
Sign In·View Thread·Permalink
AnswerRe: conversion of recursive to loopmemberWoong Gyu La14 Mar '13 - 15:58 
If you have read the article carefully, your algorithm can be replaced with loop version very easily.
However I believe this is not a place where you ask people around to do your homework.
If you really need help, show what you tried and what is not working out, then I will be happy to help you.
 
p.s. I've converted your recursive version with loop version within 10 minutes.
If you show that you really tried and if it is not really working out, then I would like to help you with the solution.
Sign In·View Thread·Permalink
GeneralMy vote of 5memberPhilippe Chessa12 Nov '12 - 22:49 
Very usefull, clear and precise. A brillant article.
Sign In·View Thread·Permalink
GeneralRe: My vote of 5memberWoong Gyu La19 Dec '12 - 19:23 
Thank you!
Sign In·View Thread·Permalink
GeneralMy vote of 5memberMichael Haephrati מיכאל האפרתי30 Oct '12 - 12:05 
very interesting article
Sign In·View Thread·Permalink
GeneralRe: My vote of 5memberWoong Gyu La19 Dec '12 - 19:22 
Thanks for the vote
Sign In·View Thread·Permalink
GeneralMy vote of 4memberEdward Keningham11 Aug '12 - 3:24 
Very well, thank you for sharing, could be useful
Sign In·View Thread·Permalink
GeneralRe: My vote of 4memberWoong Gyu La17 Sep '12 - 22:50 
Thanks
Sign In·View Thread·Permalink
GeneralMy vote of 5memberMihai MOGA8 Aug '12 - 5:27 
This is a great inspiring article. I am pretty much pleased with your good work. You put really very helpful information. Keep it up once again.
Sign In·View Thread·Permalink
GeneralRe: My vote of 5memberWoong Gyu La17 Sep '12 - 22:50 
Thanks for your vote
Sign In·View Thread·Permalink
GeneralMy vote of 4memberMarco Sorich23 Jul '12 - 3:06 
Good article for an interesting solution.
Sign In·View Thread·Permalink
GeneralRe: My vote of 4memberWoong Gyu La25 Jul '12 - 15:41 
Thank you for your vote!
Sign In·View Thread·Permalink
GeneralMy vote of 5membergndnet18 Jul '12 - 22:27 
nice
Sign In·View Thread·Permalink
GeneralRe: My vote of 5memberWoong Gyu La20 Jul '12 - 13:36 
Thank you for your vote!
Sign In·View Thread·Permalink
GeneralMy vote of 5memberPaul H Kim15 Jul '12 - 19:52 
Extremely helpful
Sign In·View Thread·Permalink
GeneralRe: My vote of 5memberWoong Gyu La20 Jul '12 - 13:35 
Thank you for your vote!
Sign In·View Thread·Permalink
GeneralMy vote of 5membervivekvijay14 Jul '12 - 0:46 
highly informative
Sign In·View Thread·Permalink
GeneralRe: My vote of 5memberWoong Gyu La14 Jul '12 - 4:08 
Thanks
Sign In·View Thread·Permalink
GeneralFirst Rule: Refactoring = Define sufficient tests first before refactoringmemberAndreas Gieriet13 Jul '12 - 23:31 
Eliminating recursion on a recursive *implementation* is a typical refactoring[^] task.
Quote:
Before refactoring a section of code, a solid set of automatic unit tests is needed.

No adequate tests --> don't refactor. So, your first and most important rule should be: define automated unit tests that check the refactored code.
 
BTW: I fully agree with Matt's comment[^] that your rule set basically replace the implicit stack implementation by an explicit hand crafted stack implementation. In that case, I prefer the implicit one over the hand crafted one since the risk of adding errornous code is smaller.
 
My advise would rather be:
1) try to convert the recursion into direct recursion
2) then into tail recursion
3) and finally convert the tail recursion into a loop
 
Employing a hand-crafted stack is not the general solution (it may need some stack some times but not to replace all call parameters and local variables, but rather to have some nested state of a particular item that is calculated).
 
So, overall, since it is rather misleading advise, a 3 only from my side.
 
Cheers
Andi
Sign In·View Thread·Permalink
GeneralRe: First Rule: Refactoring = Define sufficient tests first before refactoringmemberWoong Gyu La14 Jul '12 - 4:03 
Very good point that you made. As I said in introduction, it is to help novice developers to avoid the stack overflow when they use the recursive functions. Of course, the professional developer should do as you proposed or the way, which fits the situation, but it requires time and experiences to do everything properly. And as I also said that I agree with Matt's comment, it is just moving the stack from call stack to heap stack, which is just simulating the recursive function, but I thought it might be helpful to some novice developer when they first faced the stack-overflow before they get to know the proper way to handle all the situation.
 
p.s. Of course the unit test is really important, but just it was not the point of article here, so I just avoid mentioning.
 
After all, thank you for your feedback.
Sign In·View Thread·Permalink
GeneralCall stack vs stack<SnapShotStruct>??memberMatt T Heffron13 Jul '12 - 7:35 
It appears that a lot of this is just moving the recursion information from the call stack to a "heap" stack. The recursion isn't really "unrolled" (at least in some cases.)
For example (from the source code TailRecursion.h):
int FibNum2(int n, int x, int y)
{   
  if (1 == n)	
  {
    return y;
  }
  else	
  {
    return FibNum2(n-1, y, x+y);
  }
}
is rewritten to:
int FibNum2Loop(int n, int x, int y)
{
  // (First rule)
  struct SnapShotStruct // this can be declared as local structure
    //   since it will be only used within this function.
  {
    int inputN;    // parameter that changes
    int inputX;    // parameter that changes
    int inputY;    // parameter that changes
    // no local variable
  };
 
  // (Second rule)
  int returnVal;    // the return value at the point

  // (Third rule)
  stack<SnapShotStruct> snapshotStack;
 
  // (Fourth rule)
  SnapShotStruct currentSnapshot;
  currentSnapshot.inputN = n;
  currentSnapshot.inputX = x;
  currentSnapshot.inputY = y;
 
  snapshotStack.push(currentSnapshot);
 
  // (Fifth rule)
  while(!snapshotStack.empty())
  {
    currentSnapshot=snapshotStack.top();
    snapshotStack.pop();
 
    if(currentSnapshot.inputN == 1)
    {
      // (Eighth rule && Ninth rule)
      returnVal = currentSnapshot.inputY;
      continue;
    }
    else
    {
      // (Tenth rule)

      // Create a new snapshot for calling itself
      SnapShotStruct newSnapshot;
      newSnapshot.inputN= currentSnapshot.inputN -1 ; // give parameter as parameter given 
                                                      //   when calling itself ( FibNum(n-1, y, x+y) )
      newSnapshot.inputX= currentSnapshot.inputY;     // give parameter as parameter given when 
                                                      //   calling itself ( FibNum(n-1, y, x+y) )
      newSnapshot.inputY= currentSnapshot.inputX + currentSnapshot.inputY;// give parameter as parameter given when 
                                                                          //   calling itself ( FibNum(n-1,y,x+y) )
      snapshotStack.push(newSnapshot);
      continue;
    }
  }
  // (Second rule)
  return returnVal;
}
 
This is still using a stack!
Tail recursion is the simplest recursion to eliminate.
It can (almost?) always be reduced to a simple loop.
(Good compiler/optimizers will detect this case and deal with it "automagically".)
The above can be simplified to:
int FibNum2SimpleLoop(int n, int x, int y)
{   
  while (1 != n)  // really (1 < n) is "safer"
  {
    int next_y = x + y;
    --n;
    x = y;
    y = next_y;
  }
  return y;
}
 
The "mechanical" process you present adds a great deal of complexity and seems to just shift the recursive state storage from one place to another.
Converting recursion to iteration well requires much more thinking about the problem than your process.
 
Sorry, the best I can do is Vote of 3.
Sign In·View Thread·Permalink
GeneralRe: Call stack vs stack??memberWoong Gyu La13 Jul '12 - 14:33 
Thank you for the feedback, and you really have good point.
I should have been more careful with the wording.
Yes it is actually simulating the recursive function using while-loop and heap stack by moving stack to heap stack.
Have updated the article so it won't mislead other readers anymore.
Sign In·View Thread·Permalink
GeneralMy vote of 3memberWPFanatic13 Jul '12 - 5:37 
well written, but trivial topic. If this were rated a beginner article i'd change my vote to 5.
Sign In·View Thread·Permalink
Last Visit: 31 Dec '99 - 18:00     Last Update: 25 May '13 - 11:12Refresh12 Next »

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

About Article
This article explains 10 rules (steps) for replacing the recursive functions using stack and while-loop to avoid the stack-overflow
Type Article
Licence CPOL
First Posted 11 Jul 2012
Views 41,129
Downloads 629
Bookmarked 83 times

, +
Top News

Old Japanese Man Creates Amazing Art Using Excel (Wait, Excel?)

Get the Insider News free each morning.
Related Videos
JavaScript Programming - 0905 Recursion
JavaScript: Nesting and Invoking Functions Part 4
Recursion Primer Using C++: Part 1
Recursion Primer using C++: Part 3
Compiler Patterns
Symbolic Differentiation
Recursion made simple
Iterative Quick Sort
Recursive methods using C#
Inside the Mathematical Expressions Evaluator
Debug Tutorial Part 2: The Stack
Recursion Primer Using C++: Part 2
String.Format in JavaScript
Examining Function Calls using the Console Debugger
Iterative vs. Recursive Approaches
Easy to check recursion
How to release memory pages occupied by the thread stack when possible
Memory(-Leak) and Exception Trace (CRT and COM Leaks)
File System Enumerator using lazy matching
How to Think Like a Functional Programmer
Crafting an interpreter Part 1 - Parsing and Grammars
QuickFill: An efficient flood fill algorithm.
Permalink | Advertise | Privacy | Mobile
Web02 | 2.6.130523.1 | Last Updated 10 Aug 2012
Article Copyright 2012 by Woong Gyu La
Everything else Copyright © CodeProject, 1999-2013
Terms of Use
Layout: fixed | fluid