how to rewrite a recursive method by using a stack?

Question

Since C# doesn't support the optimization of recursive call very well (e.g tail recursion). It seems I have to switch my code style from functional programming to something I am not familiar with.

I know sometimes iterative method alternative exists to a recursion method, but usually it is quite hard to find an efficient one.

Now, in generally, I believe all recursive methods can be rewritten by using stack<T> data structure somehow.

Where can I find the tutorial or introduction or general rule to this?

e.g., what if I wanna rewrite greatest common divisor method? given m>n

    int gcd(int m, int n)
     {
          if (n==0)
             return m;
          else
              return gcd(n,m%n);
      }

Update

Probably it is a bad example as it indeed is tail recursive. Plz just ignore the fact and consider it is a normal recursive method.

Answer 1

Since your example method is tail-recursive, translating it to iterative style is easy and does not even require an explicit stack.

Here are some steps that can be applied to any recursive function:

Step 1: Rewrite the method so it calls itself exactly once (your method already does this), has exactly one return statement, and uses if and goto instead of else, while, for and foreach:

int gcd(int m, int n)
{
    int result;

    if (n == 0)
    {
        result = m;
        goto done;
    }

    result = gcd(n, m % n);

done:
    return result;
}

Step 2: Replace the recursive call with the assignment of the new arguments to the parameters and a goto to the start of the method:

int gcd(int m, int n)
{
    int result;

start:
    if (n == 0)
    {
        result = m;
        goto done;
    }

    int old_m = m;
    m = n;
    n = old_m % n;
    goto start;

done:
    return result;
}

If the method was not tail-recursive, the method would need to save its state before the goto and restore it later again.

Step 3: Remove the gotos again:

int gcd(int m, int n)
{
    int result;

    while (true)
    {
        if (n == 0)
        {
            result = m;
            break;
        }

        int old_m = m;
        m = n;
        n = old_m % n;
    }

    return result;
}

Step 4: Make the method look nicer:

int gcd(int m, int n)
{
    while (n != 0)
    {
        int old_m = m;
        m = n;
        n = old_m % n;
    }

    return m;
}

---

Here's an example that is not tail-recursive:

int fac(int x)
{
    if (x == 0)
    {
        return 1;
    }

    return x * fac(x - 1);
}

Step 1:

int fac(int x)
{
    int result;

    if (x == 0)
    {
        result = 1;
        goto end;
    }

    result = x * fac(x - 1);

end:
    return result;
}

Step 2:

int fac(int x)
{
    Stack<int> stack = new Stack<int>();
    int result;

start:
    if (x == 0)
    {
        result = 1;
        goto end;
    }

    stack.Push(x);
    x = x - 1;
    goto start;

end:
    if (stack.Count != 0)
    {
        x = stack.Pop();
        result = x * result;
        goto end;
    }

    return result;
}

Step 3:

int fac(int x)
{
    Stack<int> stack = new Stack<int>();
    int result;

    while (true)
    {
        if (x == 0)
        {
            result = 1;
            break;
        }

        stack.Push(x);
        x = x - 1;
    }

    while (stack.Count != 0)
    {
        x = stack.Pop();
        result = x * result;
    }

    return result;
}

Step 4:

int fac(int x)
{
    Stack<int> stack = new Stack<int>();

    while (x != 0)
    {
        stack.Push(x);
        x = x - 1;
    }

    int result = 1;

    while (stack.Count != 0)
    {
        x = stack.Pop();
        result = x * result;
    }

    return result;
}

Answer 2

In this case you don't even need a stack:

int gcd(int m, int n) {

    while(n != 0) {
        int aux = m;
        m = n;
        n = aux % n;
    }

    return m;
}

In general, for every tail recursive algorithm, you don't need a stack, this is way some compiler can optimize it; but the optimization is archieved WITHOUT the use of the call stack! Tail recursion can then be archieved through a simple cycle