How do I convert a doubly recursive method to a loop?

Question

Here is my simplified doubly recursive method. It does nothing useful, but illustrates the required recursive invocations:

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

I can't quite figure how I can write this as a loop to see if performance improves.

I've corrected the example for the obvious errors.

Answer 1

Whatever can be done recursively can also be done using stacks. Assuming you only want the functionality that you have written in your example:

i1 and i2 will eventually be added to the sum of global variables n1, n2. you can sum up them and assign the result to n1 or n2 in the beginning of the code to simplify the functionality. And using a stack, you can do something like:

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

which outputs the same as the recursive code:

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

Answer 2

Try this iterative (without Stack) approach:

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

Should be called as:

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

All constants from your example are passed to function, so it is totally universal. Also, important fact is that values of n1 and n2 after completion of function will be exactly the same as after completion of your recursive approach.

---

Concerning performance:

Surely, it will give some time improvement, but not much. But it will give with big input parameters. Also my approach does not consume additional memory (recursive and stack approaches consume).

---

Update about performance:

I have tested locally your and my approaches - calling each 1 000 000 times. Results are the following:

Recursive: 225.1774 ms

Iterative: 152.1194 ms

---

[Update] If you do not need n1 and n2 after function completed you can make code shorter:

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

Ouput when calling MyWayTwo(2, 3, 10, 20, 4); :

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

Even more simplified solution:

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