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

Ответ 1

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 5

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

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

и

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

и

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

Q: Обычно ли рекурсивная версия Быстрее?       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

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

Ответ 6

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

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

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

Простой пример (в 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

Ответ 7

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

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

Wiki.