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.

There is no collection in your gcd example, why would you need a stack? what would you like to store in there? — Louis Kottmann, Sep 03 '11 at 13:36
THis is purely an example.. of course I know i don't even need to use `stack` in this case.. but it is the simplest case I can think of regarding recursion. — colinfang, Sep 03 '11 at 13:43

dtb · Accepted Answer · 2011-09-04T04:50:11.983

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

score 3 · Answer 2 · answered Sep 03 '11 at 13:40

3

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

answered Sep 03 '11 at 13:40

Simone

2,261
2
19
27

THis is purely an example.. of course I know i don't even need to use `stack` in this case.. but it is the simplest case I can think of regarding recursion. And I know how to transform the recursion to iteration. I just wanna learn how to do it in a `stack` – colinfang Sep 03 '11 at 13:44
With a tail recursive algorithm you don't need a stack! This is why compilers can optimize it! – Simone Sep 03 '11 at 13:45
In a non tail recursive algorithm you can simply rely on recursion, because you will use stack for the method invocation as well – Simone Sep 03 '11 at 13:46
What i'm saying is that the optimization is possibile only with tail recursive algorithm! i believe you when you say that c# compiler don't do that, and then you can use simple iteration without stack to simulate tail recursive algorithm like in the example! You won't never need a stack for tail recursive algorithms! – Simone Sep 03 '11 at 13:49
In a general case you will do like dlev proposed! but the optimization given to you by the use of a stack won't be that important! Only with tail recursive algorithm it's convinient to translate them in a non recursive style and the reason is because you WONT'T need a stack to do that! – Simone Sep 03 '11 at 13:53
Ok. thanks for advice, I will look into this further. I was shocked when I noticed C# doesn't get Tail optimization. And I thought maybe `stack` would prevent me from `Stackoverflow Exception` – colinfang Sep 03 '11 at 13:58
And you can, what i'm saying is that you don't need a stack to do that with tail recursion, but only a simple cycle. In the other case, with non tail recursive algos, it's really difficult to get a stackoverflow – Simone Sep 03 '11 at 14:06

score 2 · Answer 3 · answered Sep 03 '11 at 13:44

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.

score 1 · Answer 4 · answered Sep 03 '11 at 13:59

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.

how to rewrite a recursive method by using a stack?

4 Answers4

Linked