[recursion] Способ перехода от рекурсии к итерации



8 Answers

Действительно, наиболее распространенный способ сделать это - сохранить свой собственный стек. Вот рекурсивная функция быстрой сортировки в C:

void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;

    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

Вот как мы можем сделать это итеративным, сохранив свой собственный стек:

void quicksort(int *array, int left, int right)
{
    int stack[1024];
    int i=0;

    stack[i++] = left;
    stack[i++] = right;

    while (i > 0)
    {
        right = stack[--i];
        left = stack[--i];

        if (left >= right)
             continue;

        int index = partition(array, left, right);
        stack[i++] = left;
        stack[i++] = index - 1;
        stack[i++] = index + 1;
        stack[i++] = right;
    }
}

Очевидно, что этот пример не проверяет границы стека ... и действительно вы можете определить размер стека на основе наихудшего случая, учитывая левое и правое значения. Но ты получил идею.

Question

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

Итак, где-то в самом далеком прошлом я попытался найти, существует ли какой-либо «шаблон» или способ преобразования общего рекурсивного подхода к итерации и ничего не нашел. Или, по крайней мере, ничего, что я помню, не помогло бы.

  • Существуют ли общие правила?
  • Есть ли «шаблон»?



Я просто поддержал ответ, предлагающий использовать явный стек, который, по моему мнению, является правильным решением и имеет общую применимость.

Я имею в виду, что вы можете использовать его для преобразования любой рекурсивной функции в итеративную функцию. Просто проверьте, какие значения сохраняются в рекурсивных вызовах, те, которые должны быть локальными для рекурсивной функции, и заменяют вызовы циклом, в котором вы будете нажимать их на стек. Когда стек пуст, рекурсивная функция была бы прервана.

Я не могу удержаться, чтобы сказать, что доказательство того, что каждая рекурсивная функция эквивалентна итеративной функции на другом типе данных, это одна из моих самых дорогих воспоминаний о моих университетских временах. Это был курс (и профессор), который действительно заставил меня понять, что такое компьютерное программирование.




Грубое описание того, как система принимает любую рекурсивную функцию и выполняет ее с использованием стека:

Это предназначалось для демонстрации идеи без подробностей. Рассмотрим эту функцию, которая будет печатать узлы графика:

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

Например, график: A-> B A-> C show (A) будет печатать B, A, C

Функциональные вызовы означают сохранение локального состояния и точки продолжения, чтобы вы могли вернуться, а затем перейдите к функции, которую вы хотите вызвать.

Например, предположим, что show (A) начинает работать. Вызов функции в строке 3. показывает (B) означает - Добавить элемент в стек, означающий «вам нужно продолжить в строке 2 с локальным узлом состояния переменной = A» - перейти к линии 0 с узлом = B.

Для выполнения кода система выполняет инструкции. Когда встречается вызов функции, система подталкивает информацию, которая ему нужна, чтобы вернуться туда, где она была, запускает код функции, и когда функция завершается, появляется информация о том, где она должна идти, чтобы продолжить.




Стремитесь сделать свой рекурсивный вызов Tail Recursion (рекурсия, в которой последний оператор является рекурсивным вызовом). Как только вы это сделаете, преобразование его на итерацию, как правило, довольно легко.




Рекурсия - это не что иное, как процесс вызова одной функции из другого, только этот процесс выполняется путем вызова функции сам по себе. Как известно, когда одна функция вызывает другую функцию, первая функция сохраняет свое состояние (ее переменные), а затем передает управление вызываемой функции. Вызываемая функция может быть вызвана с использованием одного и того же имени переменных ex fun1 (a) может вызвать fun2 (a). Когда мы делаем рекурсивный вызов, ничего нового не происходит. Одна функция вызывает себя, передавая один и тот же тип и аналогичную переменную имени (но, очевидно, значения, хранящиеся в переменных, различны, только имя остается таким же.) Для себя. Но перед каждым вызовом функция сохраняет свое состояние, и этот процесс сохранения продолжается. СОХРАНЕНИЕ СДЕЛАНО НА СТЕК.

ТЕПЕРЬ СТЕК ПРИХОДИТ В ИГРА.

Поэтому, если вы пишете итеративную программу и каждый раз сохраняете состояние в стеке, а затем выталкиваете значения из стека, когда это необходимо, вы успешно конвертируете рекурсивную программу в итеративную!

Доказательство простое и аналитическое.

В рекурсии компьютер поддерживает стек и в итеративной версии вам придется вручную поддерживать стек.

Подумайте над этим, просто конвертируйте рекурсивную программу глубинного поиска (на графиках) в итеративную программу dfs.

Всего наилучшего!




Даже использование стека не будет преобразовывать рекурсивный алгоритм в итеративный. Обычная рекурсия - это рекурсия, основанная на функциях, и если мы используем стек, то она становится рекурсией на основе стека. Но его все еще рекурсия.

Для рекурсивных алгоритмов пространственная сложность O (N), а временная сложность O (N). Для итеративных алгоритмов сложность пространства - это O (1), а временная сложность - O (N).

Но если мы используем вещи стека с точки зрения сложности, они остаются такими же. Я думаю, что только хвостовая рекурсия может быть преобразована в итерацию.




Просто убить время ... Рекурсивная функция

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

могут быть преобразованы в

void foo(Node* node)
{
    if(node == NULL)
       return;

    // Do something with node...

    stack.push(node->right);
    stack.push(node->left);

    while(!stack.empty()) {
         node1 = stack.pop();
         if(node1 == NULL)
            continue;
         // Do something with node1...
         stack.push(node1->right);             
         stack.push(node1->left);
    }

}



Найдите google для «Продолжающийся стиль передачи». Существует общая процедура преобразования в хвостовой рекурсивный стиль; существует также общая процедура поворота хвостовых рекурсивных функций в циклы.




Существует общий способ преобразования рекурсивного обхода в итератор с помощью ленивого итератора, который объединяет несколько поставщиков итераторов (выражение лямбда, которое возвращает итератор). См. Раздел « Преобразование рекурсивного обхода в Iterator» .




Related