如何使用堆栈重写递归方法？

Question

由于C#不能很好地支持递归调用的优化(例如尾递归).看来我必须将代码风格从函数式编程转换为我不熟悉的东西.

我知道有时迭代方法替代存在于递归方法中,但通常很难找到有效的方法.

现在,一般来说,我相信所有递归方法都可以通过stack<T>某种方式使用数据结构来重写.

我在哪里可以找到教程或介绍或一般规则？

例如,如果我想重写最常见的除数方法怎么办？给定m> n

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

更新

可能它是一个坏的例子,因为它确实是尾递归.Plz只是忽略了这个事实并认为它是一种正常的递归方法.

Answer 1

由于您的示例方法是尾递归的,因此将其转换为迭代样式很容易,甚至不需要显式堆栈.

以下是可以应用于任何递归函数的一些步骤:

第1步:重写方法,因此调用自身一次(你的方法已经这样做了),都只有一个return语句,使用if和goto替代else,while,for和foreach:

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

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

    result = gcd(n, m % n);

done:
    return result;
}

步骤2:使用参数的新参数赋值替换递归调用,并将a替换goto为方法的开头:

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

如果该方法不是尾递归的,则该方法需要在其之前保存其状态,goto并在以后再次恢复它.

第3步:goto再次删除s:

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

第4步:使方法看起来更好:

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

    return m;
}

这是一个不是尾递归的例子:

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

    return x * fac(x - 1);
}

步骤1:

int fac(int x)
{
    int result;

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

    result = x * fac(x - 1);

end:
    return result;
}

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

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

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