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





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

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

recursion computer-science theory iteration

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

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

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



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




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

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

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




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




Как правило, метод предотвращения переполнения стека для рекурсивных функций называется техникой батута, которая широко используется разработчиками Java.

Однако для C # здесь есть небольшой вспомогательный метод, который превращает вашу рекурсивную функцию в итеративную, не требуя изменения логики или сделать код понятным. C # - такой приятный язык, что с ним можно наслаждаться потрясающим материалом.

Он работает путем обертывания частей метода вспомогательным методом. Например, следующая рекурсивная функция:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

Превращается в:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}



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

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

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




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

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

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

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

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

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

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




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

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

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.

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




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






Related