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

Question

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

我知道有时迭代方法可以替代递归方法，但通常很难找到有效的方法。

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

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

例如，如果我想重写最大公约数方法怎么办？给定 m>n

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

更新

可能这是一个不好的例子，因为它确实是尾递归的。请忽略这个事实，认为这是一个正常的递归方法。

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 步:将递归调用替换为将新参数分配给参数并将 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:

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