Recursive function to loop and stack

Question

It's well known all recursive functions can be written using just a single loop and a stack. Although this conversion can be criticized to be ugly or less readable, its main use is obviously to avoid smashing the heap.

There are natural ways to convert simple recursive functions into loops. For instance, take the simple tail-recursion elimination using an accumulator. So far, I have not seen yet a definitive answer for this question.

At least to me, sometimes it seems black magic to convert such recursive functions into loops provided a stack. For instance, think of writing a non-recursive version for

f(n) = n,                    if n <= 1
f(n) = f(n-1) + f(n-2) + 1,  if n > 1

The very point underlying this question is:

• Is there a lucid, general method to convert a recursive function into a loop + stack?

Answer 1

Feasibility (100%):

From here, we know that any recursive function can be converted to iterate (into a loop) but you need to use a stack yourself to keep the state.

---

How to do this (generally):

You can check out the article How to replace recursive functions using stack and while-loop to avoid the stack-overflow, which gives examples and steps (10 steps/rules) on how to convert recursive functions to stack and while-loop. See the following part for real example.

---

Example:

Take the following recursive function as an example:

// 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;
} 

After applying the 10 rules/steps introduced in the article (details shown in comments), you will get:

// 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;
} 

---

BTW, the above article is the Prize winner in Competition <Best C++ article of July 2012> of CodeProject, so it should be trust-able. :)

Answer 2

Yes, but the solution won't be much better than the recursive one except maybe reduce the chance for a stack overflow.

By looking at the sequence, which is similar to the Fibonacci sequence except you add 1 to the result for every round except n = (0,1), you see a pattern.

0 1 2 4 7 12 20 
    \  \___ ...\____
    0+1+1  1+2+1   7+12+1

Since the whole generation is dependent on the two previous numbers you can have two variables in a loop representing that and you don't need to have a stack at all.

//intentional generic algol dialect
int modfib (int n)
{
    if( n <= 1 )
      return n;
    n = n - 2;
    int a=2;
    int b=4;
    int tmp;
    while( n-- > 0 )
    {
        tmp=a;
        a=b;
        b = tmp + b +1;
    }
    return a;
}

Until compilers know to do this we still need humans to optimize code.