Шаблоны проектирования для преобразования рекурсивных алгоритмов в итерационные

Question

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

Answer 1

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

Answer 2

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

Проверьте следующие статьи:

• Замена рекурсии стеком
• Стеки и устранение рекурсии (pdf)

Answer 3

Обычной практикой является для управления стеком LIFO, который хранит текущий список того, что «еще предстоит сделать» , и для обработки всего процесса в цикле while, который продолжается до тех пор, пока список не станет пустым.
С этим шаблоном то, что будет рекурсивным вызовом в истинной модели рекурсии, заменяется на
- вставка «контекста» текущей (частично завершенной) задачи в стек
- перенос новой задачи (той, которая вызвала рекурсию) в стек
- и "продолжить" (то есть перейти к началу) цикла while. Рядом с заголовком цикла логика выводит последний вставленный контекст и начинает работать на этой основе.

Фактически это просто "перемещает" информацию , которая в противном случае хранилась бы во вложенных стековых фреймах в "системном" стеке, в контейнер стека, управляемого приложением. Однако это является улучшением, поскольку этот контейнер стека может быть размещен где угодно (предел рекурсии обычно привязан к ограничениям в «системном» стеке). Поэтому, по сути, выполняется та же самая работа, но явное управление «стеком» позволяет выполнять это в рамках конструкции с одним циклом, а не в рекурсивных вызовах.

Answer 4

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

Например, стандартное общерекурсивное определение факториала

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

можно заменить на

 factorial(n) = f_iter(n, 1)

и

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

который является хвостовым рекурсивным. Это так же, как

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

Answer 5

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

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

Идея состоит в том, чтобы начать с базового варианта (или базовых вариантов) и использовать его для построения решения для более крупных случаев, а затем использовать их для построения еще более крупных случаев и т. Д., Пока вся проблема не будет решена. Это не требует стека, и может быть сделано с циклами.

Простой пример (на Python):

#recursive version
def fib(n):
     if n==0 or n==1:
             return n
     else:
             return fib(n-1)+fib(n-2)

#iterative version
def fib2(n):
     if n==0 or n==1:
             return n
     prev1,prev2=0,1 # start from the base case
     for i in xrange(n):
             cur=prev1+prev2 #build the solution for the next case using the previous solutions
             prev1,prev2=cur,prev1
     return cur

Answer 6

Посмотрите эти ссылки для примеров производительности

Итерация VS-рекурсии (цикл): сравнение скорости и памяти

и

Заменить рекурсию на итерацию

и

Рекурсия против итерации

В: Обычно это рекурсивная версия Быстрее? A: Нет - обычно это медленнее (из-за накладных расходов на поддержание стек)

  Q: Does the recursive version usually use less memory?
  A: No -- it usually uses more memory (for the stack).

  Q: Then why use recursion??
  A: Sometimes it is much simpler to write the recursive version (but

нам нужно подождать, пока мы обсуждали деревья, чтобы увидеть действительно хорошо примеры ...)

Answer 7

Один шаблон - Хвостовая рекурсия :

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

Wiki .