how to rewrite a recursive method by using a stack?

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 tuto开发者_StackOverflow中文版rial 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.

---

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

---

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

---

If we look at the simplest case, it shouldn't be too hard to generalize from there.

Suppose we have a method that looks like this:

public void CountToTenInReverse(int curNum)
{
    if (curNum >= 11)
        return;

    CountToTen(curNum + 1);
    Console.WriteLine(curNum);
}

Let's look at the call stack for CountToTenInReverse(1) to see what's actually happening. After ten calls, we have this:

[ CountToTenInReverse(10) ]      <---- Top of stack
[ CountToTenInReverse(9) ]
[ CountToTenInReverse(8) ]
[ CountToTenInReverse(7) ]
[ CountToTenInReverse(6) ]
[ CountToTenInReverse(5) ]
[ CountToTenInReverse(4) ]
[ CountToTenInReverse(3) ]
[ CountToTenInReverse(2) ]
[ CountToTenInReverse(1) ]       <---- Bottom of stack

After the tenth call, we'll hit the base case, and start unwinding the stack, printing numbers as we go. In words, then, our algorithm is "Push numbers onto the stack, stop when we hit 10 numbers, and then pop and print each number." So let's write that with our own stack:

public void PrintToTenInReverseNoRecursion()
{
    Stack<int> myStack = new Stack<int>();

    for (int i = 0; i < 10; i++)
    {
        myStack.Push(i);
    }

    for (int i = 0; i < 10; i++)
        Console.WriteLine(myStack.Pop());
}

And now we've successfully converted it over. (Of course this can be done iteratively without a stack, but it was just an example.)

The same approach can be taken for other, more complicated algorithms: look at the call stack, and then imitate what it's doing with your own stack.

---

I know this doesn't really answer your question on how to program a recursive call with a Stack, but .NET does support optimization of tail calls. It's not as simple or straight-forward as a compiled language because of the presence of a JIT compiler and the translation of IL between different CLR language compilers.

That said, why worry about it? If it is a performance problem, rewrite the method and eliminate the recursive call altogether. Also, be aware that .NET 4.0 has made vast improvements in this area. Here is some more information on Tail Call Improvements in .NET Framework 4. You might be worrying about a non-issue.