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

本文关键字：递归方法 重写 堆栈 何使用 | 更新日期: 2023-09-27 18:07:19

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

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

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

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

。如果我想重写最大公约数法呢?鉴于m> n 

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

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

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

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

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

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

在这种情况下，你甚至不需要堆栈:

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

一般来说，对于每个尾部递归算法，你不需要堆栈，这是一些编译器可以优化它的方式;但优化是在没有使用调用堆栈的情况下实现的!然后可以通过一个简单的循环

实现尾部递归

如果我们看一下最简单的情况，从那里归纳应该不难。

假设我们有这样一个方法:

public void CountToTenInReverse(int curNum)
{
    if (curNum >= 11)
        return;
    CountToTen(curNum + 1);
    Console.WriteLine(curNum);
}

让我们看看CountToTenInReverse(1)的调用堆栈，看看实际发生了什么。调用10次之后，我们得到这个:

[ 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

在第十次调用之后，我们将到达基本情况，并开始展开堆栈，同时打印数字。换句话说，我们的算法是"将数字压入堆栈，当我们到达10个数字时停止，然后弹出并打印每个数字。"那么让我们用我们自己的堆栈来写:

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

现在我们成功地转换了它。(当然，这可以在没有堆栈的情况下迭代地完成，但这只是一个示例。)

同样的方法可以用于其他更复杂的算法:查看调用堆栈，然后模仿它在您自己的堆栈中所做的事情。

我知道这并不能真正回答你关于如何用堆栈编程递归调用的问题，但是。net确实支持尾部调用的优化。它不像编译语言那样简单或直接，因为存在JIT编译器和不同CLR语言编译器之间的IL转换。

话虽如此，何必担心呢?如果是性能问题，则重写方法并完全消除递归调用。此外，请注意。net 4.0在这方面做了巨大的改进。这里有一些关于。net Framework 4中尾部调用改进的更多信息。你可能在担心一个无关紧要的问题。

相关文章：