如何将双递归方法转换为循环？

Question

这是我的简化双递归方法。它没有实际用途，但说明了所需的递归调用：

void Main()
{
    Test(2, 3, 4);
}

int n1 = 0;
int n2 = 0;

void Test(int i1, int i2, int v)
{
    if (v == 0)
    {
        (n1 + n2).Dump();
    }
    else
    {
        n1 = i1 + 10;
        n2 = i2 + 20;
        Test(n1, n2, v - 1);
        Test(n2, n1, v - 1);
    }   
}

我不太清楚如何编写一个循环来查看性能是否会提高。

我已经纠正了这个例子中明显的错误。

- descf

---

是的，可以使用迭代方法更快地完成。我的方法（在我的答案中）在测试v=25时大约快2倍。 - SergeyS

Answer 1

任何可以通过递归实现的功能都可以使用栈来实现。假设您只需要您示例中编写的功能：

i1和i2最终会添加到全局变量n1、n2的总和中。您可以在代码开头将它们相加并将结果赋值给n1或n2，以简化功能。同时，使用栈，您可以这样实现：

int n1 = 0;
int n2 = 0;

void Test2(int i1, int i2, int v)
{
    Stack<int> s = new Stack<int>(new[] {v});
    n1 = i1 + i2;

    while (s.Any())
    {
        v = s.Pop();
        if (v == 0)
        {
            Console.Out.WriteLine(n1 + n2);
        }
        else
        {
            int tmp = n1;
            n1 = n2 + 10;
            n2 = tmp + 20;
            s.Push(v - 1);
            s.Push(v - 1);
        }
    }
}

输出与递归代码相同的代码如下：

125
155
155
215
215
245
245
335
335
365
365
425
425
455
455

- Faruk Sahin

---

太好了！它起作用了！只有一个问题...你是怎么想到 n1 = i1 + i2 的？ - Aditi

+1 我不确定这样做是否会带来任何性能提升，因为这是编译器通常实现递归调用的方式。不过这是一个不错的替代方案。 - Totero

这也可以不用堆栈来实现。 - SergeyS

@SergeyS，与其运行相同测试1,000,000次，使用更大的v值运行测试可能是更好的测试，因为创建Stack对象具有相当高的开销。虽然我没有考虑任何性能提升，但我只是想展示如何使用堆栈重写递归代码的快速示例。 - Faruk Sahin

@Faruk Sahin - 我也尝试了一次v=25的运行，你的方法仍然比递归方法慢。我并不是说它不好，只是好奇。 - SergeyS

Answer 2

尝试使用迭代（无需堆栈）的方法：

int n1 = 0;
int n2 = 0;

void MyWay(int start1, int start2, int plus1, int plus2, int v)
{
    n1 = start2 + plus2 * v;
    n2 = start1 + plus1 * v;
    for (int i = 0, pow = 1 << v; i < pow; i++)
    {
        if ((i & 1) == 0)
        {
            int temp = n2;
            n2 = n1;
            n1 = temp;
        }
        for (int mask = i; mask > 0 && (mask & 1) == 0; mask >>= 1)
        {
            n1 += plus1;
            n2 += plus2;
        }
        Console.WriteLine(n1 + n2);
    }
}

应该这样调用：

MyWay(2, 3, 10, 20, 4);

你的示例中的所有常量都被传递给了函数，因此它是完全通用的。 另一个重要的事实是，在完成函数后，n1和n2的值将与您的递归方法完成后的值完全相同。

关于性能： 当然，这样做会提高一些时间，但不是很多。但是对于大的输入参数来说，这将有所改善。 此外，我的方法不消耗额外的内存（递归和堆栈方法会消耗）。

有关性能的更新： 我已经在本地测试了您和我的方法-每个方法都调用1000000次。 结果如下：

递归：225.1774毫秒 迭代：152.1194毫秒

[更新]如果您在函数完成后不需要n1和n2，则可以使代码更短：

void MyWayTwo(int start1, int start2, int plus1, int plus2, int v)
{
    plus1 += plus2;
    int n = start1 + start2 + plus1 * v;
    for (int i = 0, pow = 1 << v; i < pow; i++)
    {
        for (int mask = i; mask > 0 && (mask & 1) == 0; mask >>= 1)
            n += plus1;
        Console.WriteLine(n);
    }
}

调用MyWayTwo(2, 3, 10, 20, 4);时的输出:

125
125
155
155
215
215
245
245
335
335
365
365
425
425
455
455

更加简化的解决方案：

void MyWayTwo(int s1, int s2, int p1, int p2, int v)
{
    p1 += p2;
    s1 += s2;
    for (int i = 1 << v, p = i << 1; i < p; i++)
    {
        for (int m = i; (m & 1) == 0; m >>= 1)
            s1 += p1;
        Console.WriteLine(s1);
    }
}

- SergeyS

Answer 3

如果您只想使用最终结果，我可以给您这段代码。

protected void TestIt(int i1, int i2, int v)
{
    int tot = 0;
    for (; v > 0; v--)
        tot = tot * 2 + 30;
    Console.Out.WriteLine(tot + i1 + i2);
}

如果你需要中间结果，不幸的是这段代码无法提供。

- Destrictor