5 replies to this topic

[ThemePark]

I have this recursive function that I need to convert an iterative function:

public void function() {
  first_line
  ..
  line_before
  function();
  line_after
  ..
  last_line
}

So in the iterative version, when I've executed line_before, I would jump back to first_line again. And when I reach last_line, I would then jump to line_after. However, since it's mostly some if sentences I can't use continue to jump in the code. So what else can I do to convert my function?

[Alexander]

Can you provide a more working function? I can not wrap my head around what to recommend with just that.

[WingedPanther]

The process of converting a recursive function to a non-recursive function depends HEAVILY on the details of how the function works and what it does. In some cases it is trivial, in other cases it requires completely changing the logic of the algorithm, in still others it's impossible.

[zoranh]

To understand how recursion works you should know that local variables are stored on call stack in a sequence of locations called Stack Frame. When new recursive call
is made, new stack frame is pushed to call stack, hence new instances of local variables are allocated in memory.

If you want to convert recursion into iteration, one way is to do that is to mimic call stack.

You can design a class which is specific for your function (lets call it Frame, like stack frame) of which objects represent current execution state of a function.
If function returns value, then Frame class must contain a field which contains return value.
All lines in a function operate on that object, rather than on local variables. The only allowed local variable is a stack of Frame objects.

Then convert function starting with these guidelines:
1. Entry point of function dequeues Frame from stack.
2. Return statement is replaced with statements which gets current Frame's return value and discards current Frame;
then pop new Frame from stack and (if available) sets return value to appropriate variable in popped Frame.
3. Recursive call is replaced by creating new Frame and setting its fields which represent function arguments.
4. All other statements are changed to access fields in Frame, rather than local variables.

Now let's construct such solution (this is language-independant, works for Java or anything else):

retType f(arg1, arg2, ... argN)
{
    
    statement1;
    statement2;
    ...
    statementP;
    
    if (condition1)        // This was missing in your example - recursive calls must end somewhere!
        x = f(v11, v12, ..., v1N);
    
    statementP+1;
    ...
    statementQ;
    
    if (condition2)        // Multiple recursive calls make general case
        y = f(v21, v22, ..., v2N);
    
    statementQ+1;
    ...
    statementR;
    
    return retVal;
    
}

This function is converted into this form:

retType f(arg1, arg2, ..., argN)
{

    retType retVal = default;
    
    // Initialize call at depth 1:
    Stack frameStack = new Stack();
    Stack stageStack = new Stack();
    Frame f = new Frame();
    f.arg1 = arg1;
    f.arg2 = arg2;
    ...
    f.argN = argN;

    // stages: 1 - statements 1-P, 2 - statements (P+1)-Q, 3 - statements (Q+1)-R, 4 - return statement
    frameStack.push(f);    // this means that frame f is being executed at stage 1
    stageStack.push(1);
    
    // while there is current frame, keep going
    while (!frameStack.IsEmpty())
    {
    
        f = frameStack.Pop();
        int stage = stageStack.Pop();
        
        frameStack.Push(f);
        stageStack.Push(stage + 1);
        
        switch (stage)
        {
            case 1:
                
                statement1(f);
                ...
                statementP(f);
                
                // Now make recursive call
                if (f.condition1())
                {
                    Frame f1 = new Frame();
                    f1.arg1 = f.stage1Arg1;
                    f1.arg2 = f.stage1Arg2;
                    ...
                    f1.argN = f.stage1ArgN;
                    
                    frameStack.Push(f1);
                    stageStack.Push(1);
                }
                
                break;
            case 2:
            
                statementP+1(f);
                ...
                statementQ(f);
                
                // Now make recursive call
                if (f.condition2())
                {
                    
                    Frame f1 = new Frame();
                    f1.arg1 = f.stage2Arg1;
                    f1.arg2 = f.stage2Arg2;
                    ...
                    f1.argN = f.stage2ArgN;
                    
                    frameStack.Push(f1);
                    stageStack.Push(1);
                    
                }
                break;
            case 3:
            
                statementQ+1(f);
                ...
                statementR(f);
                
                // Now execute return statement:
                retVal = f.retVal;
                frameStack.Pop();
                stageStack.Pop();
                
                // If call depth is greater than 1, then retVal must be passed to previous frame:
                // If call depth is 1, execution will stop after this point, 
                // and retVal local variable will contain overall return value of the function
                if (!frameStack.IsEmpty())
                {
                    Frame parent = frameStack.Pop();
                    parent.calledRetVal = retVal;
                    frameStack.Push(parent);    // Return frame to stack so that its execution continues, having retVal of recursive call available
                }
                
                break;
                
        }
        
    }
    
    return retVal;

}

[zoranh]

More specific case is so-called tail recursion. That is the case in which recursive call is the last call in function and function returns void. I'm writing this as new post because it solves different problem compared to previous post.

Here is the function with tail recursive call:

void f(arg1, arg2, ..., argN)
{

    statement1;
    statement2;
    ...
    statementM;
    
    if (condition)
        f(arg11, arg12, ..., arg1N);
        
}

This is transformed into iteration without the stack:

void f(arg1, arg2, ..., argN)
{

    bool done = false;
    // Here declare local variables
    
    while (!done)
    {
        
        // Here initialize local variables - clear them to initial values in each iteration
        // because each iteration represents new stack frame
        
        statement1;
        statement2;
        ...
        statementM;
        
        if (!condition)
            done = true;    // this stops re-entering statement1, i.e. stops recurrent calls
        else
        {
            arg1 = newArg1Value    // now set values to arguments with which recursive call would normally be made
            arg2 = newArg2Value;
            ...
            argN = newArgNValue;
        }

            
    }

}

[zoranh]

Here is a notorious example of converting recursion to a more optimal iteration. Solving factorial problem can look like this (in C#):

int fact(int n)
{

    int result = 1;

    if (n > 1)
        result = n * fact(n - 1);

    return resutl;
    
}

This can be converted to an iteration. First, remove return statement for clarity (it will be added later), and change the code so that recursive call is the last statement in function:

void fact(int n, ref int f)
{

    if (n < 1 && f == 0)
        f = 1;
        
    if (n > 1)
        f *= n;
        
    if (n > 1)
        fact(n - 1, ref f);

}

Now we have a better understanding what return statement is - it is actually an action of writing a result into specific location at the caller's address space.
Now convert this into iteration:

void  fact(int n, ref int f)
{

    bool done = false;
    
    while (!done)
    {

        if (n < 1 && f == 0)
            f = 1;
    
        if (n > 1)
            f *= n;
            
        if (n > 1)
            n--;    // reiterate with n reduced by 1
        else
            done = true;
            
    }
    
}

Now convert this code into function which returns value:

int fact(int n)
{

    bool done = false;
    int f = 0;
    
    while (!done)
    {
        
        if (n < 1 && f == 0)
            f = 1;
            
        if (n > 1)
            f *= n;
            
        if (n > 1)
            n--;
        else
            done = true;
            
    }
    
    return f;

}

At the end, optimize this code:

int fact(int n)
{

    int f = 1;
    
    while (n > 1)
        f *= n--;
        
    return f;

}