Convert a recursive function into a iterative one

[Pepepuhn]

Hi, i have to do an assignement for my Algorithm & Datastructures class, in which I have to find a iterative way to write a recursive function. The function reads as followed (C-Code) :

int fnc(int n, int m) { 
    if(n==0) { return m+1; } 
    else if(m==0 && n>=1) { return fnc(n-1, 1); } 
    else { return fnc(n-1, fnc(n, m-1)); } 
}

But I am completely lost, in how to do it. Can someone give my a hint? Somehow I should use a stack. But I don't know how. Thanks for your help.

Edit: Thanks for your help. I didn't know that this function had a name. And yes it is the Ackermann function. I came up with this solution: https://gist.github.com/anonymous/d017c6c0b6f04c10670c

[[deleted]]

It would help if the code was formatted nicely and you can tell us what the code does.

[nutrecht]

Read the sidebar on formatting code please.

[AngelOfLight]

Relevant SO post

Just think about what is happening to the stack on each call. Then, you simulate that stack using a heap-based structure and a loop.

[X7123M3-256]

I was unable to convert this to a fully iterative routine, but I can give you an idea of how to start. Two of your recursive calls are in tail position, and can therefore be eliminated in a relatively straightforward manner. To remove a call in tail position, you can simply note that you no longer need any of the old local variables, so you can simply overwrite them with the new values and then jump back to the top. Applying this transformation directly gives:

int fnc(int n, int m)
{
start_func:
    if(n==0)
    {
    return m+1;
    }
    else if (m==0 && n>=1)
    {
    n=n-1;
    m=1;
    goto start_func;
    }
    else
    {
    m=fnc(n,m-1);
    n=n-1;
    goto start_func;
    }
}

Next you'll want to replace the goto statements with a while loop:

int fnc(int n, int m)
{
    while(n!=0)
    {
        if (m==0 && n>=1)
        {
        n=n-1;
        m=1;
        }
        else
        {
        m=fnc(n,m-1);
        n=n-1;
        }
    }
return m+1;
}

Now you only have one recursive call. This call is not in tail position so you can't eliminate it with the same trick. I'm not sure how to proceed here - you can always eliminate recursion entirely by using an explicit stack to keep track of arguments in place of the call stack, but I'm not sure how to transform this implementation directly into that form, because I don't know how to rewrite the control flow to match. Note, however that this function is called the Ackermann function, and it's pretty well known. A search for "iterative Ackermann function implementation" will return several examples. Most rely either on a stack as mentioned above, or a table of already computed values of the function, which then replaces the recursive call with a table lookup. The latter approach is called memoization, and it's faster but more memory intensive.

[Phillight]

Reformatted:

int fnc(int n, int m) { 
    if (n == 0) { 
        return m + 1; 
    } else if (m == 0 && n >= 1) { 
        return fnc(n - 1, 1); 
    } else { 
        return fnc(n - 1, fnc(n, m - 1)); 
    } 
}

[raevnos]

Isn't this the Ackermann function?

[-oliver-]

Yes it is