如何将双重递归方法转换为循环
本文关键字:转换 循环 递归方法 | 更新日期: 2023-09-27 17:53:04
这是我简化的双重递归方法。它没有做任何有用的事情,但说明了所需的递归调用:
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);
}
}
我不太明白我怎么能把这个写成一个循环来看看性能是否提高。
我已经纠正了这个例子中明显的错误
任何可以递归完成的都可以使用堆栈完成。假设您只需要您在示例中编写的功能:
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
尝试这种迭代(不使用Stack)方法:
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的值与递归方法完成后的值完全相同。
关于性能:
当然,它会给一些时间的改善,但不是很多。但是它会在大的输入参数下给出。此外,我的方法不消耗额外的内存(递归和堆栈方法消耗)。
性能更新:
我已经在本地测试了你和我的方法——分别拨打100万次电话。结果如下:
递归:225.1774 ms
迭代:152.1194 ms
[Update]如果功能完成后不需要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);
}
}
如果你只想使用最终结果,我可以给你这个代码
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);
}
如果你需要中间结果,不幸的是这段代码不能给你。