Подтвердить что ты не робот

Как преобразовать дважды рекурсивный метод в цикл?

Вот мой упрощенный двухрекурсивный метод. Он ничего не полезен, но иллюстрирует требуемые рекурсивные вызовы:

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

Я не могу понять, как я могу написать это как цикл, чтобы увидеть, улучшена ли производительность.

Я исправил пример для очевидных ошибок.

Ответ 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);
        }
    }
}

который выводит то же самое, что и рекурсивный код:

Ответ 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 после завершения функции будут точно такими же, как после завершения вашего рекурсивного подхода.

Что касается производительности:

Конечно, это даст некоторое время, но не так много. Но это даст большие входные параметры. Также мой подход не потребляет дополнительную память (потребляют рекурсивные и стековые подходы).

Обновление производительности:

Я тестировал локально ваши и мои подходы - называя каждый 1 000 000 раз. Результаты следующие:

Рекурсивный: 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);:

Еще более упрощенное решение:

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

Ответ 3

Если вы хотите использовать только endresult, я могу дать вам этот код

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

если вам нужны промежуточные результаты, к сожалению, этот код не сможет дать вам.