Может ли каждая рекурсия быть преобразована в итерацию? - PullRequest
174 голосов
/ 31 мая 2009

A reddit thread поднял интересный вопрос:

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

Примером (счетчика?) В сообщении является пара:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Ответы [ 18 ]

176 голосов
/ 01 июня 2009

Вы всегда можете превратить рекурсивную функцию в итеративную? Да, безусловно, и тезис Черч-Тьюринга доказывает это, если память служит. Проще говоря, в нем говорится, что то, что вычислимо рекурсивными функциями, вычислимо итерационной моделью (такой как машина Тьюринга) и наоборот. Тезис не говорит вам точно, как сделать преобразование, но он говорит, что это определенно возможно.

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

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

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

Я вижу одну вескую причину. Предположим, у вас есть прототип системы на языке сверхвысокого уровня, например [ надевающее асбестовое белье ] Scheme, Lisp, Haskell, OCaml, Perl или Pascal. Предположим, что условия таковы, что вам нужна реализация на C или Java. (Возможно, это политика.) Тогда вы, конечно, могли бы написать некоторые функции рекурсивно, но которые, буквально переведенные, взорвали бы вашу систему времени выполнения. Например, бесконечная хвостовая рекурсия возможна в Схеме, но та же идиома создает проблему для существующих сред Си. Другим примером является использование лексически вложенных функций и статической области видимости, которые поддерживает Pascal, но не поддерживает C.

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

38 голосов
/ 02 ноября 2009

Всегда ли можно написать нерекурсивную форму для каждой рекурсивной функции?

Да. Простое формальное доказательство состоит в том, чтобы показать, что как µ рекурсия , так и нерекурсивное исчисление, такое как GOTO, являются полными по Тьюрингу. Поскольку все полные исчисления Тьюринга строго эквивалентны по своей выразительной силе, все рекурсивные функции могут быть реализованы нерекурсивным исчислением Полного Тьюринга.

К сожалению, я не могу найти хорошее, формальное определение GOTO онлайн, поэтому вот оно:

Программа GOTO представляет собой последовательность команд P , выполняемых на регистрационной машине , так что P является одной из следующих:

  • HALT, что останавливает выполнение
  • <em>r</em> = <em>r</em> + 1, где <em>r</em> - любой регистр
  • <em>r</em> = <em>r</em> – 1, где <em>r</em> - любой регистр
  • GOTO <em>x</em>, где <em>x</em> - метка
  • IF <em>r</em> ≠ 0 GOTO <em>x</em>, где <em>r</em> - любой регистр, а <em>x</em> - метка
  • Метка, сопровождаемая любой из вышеперечисленных команд.

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

Для получения дополнительной информации см. этот ответ .

27 голосов
/ 31 мая 2009

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

12 голосов
/ 31 мая 2009

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

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

9 голосов
/ 23 марта 2013
  • Поток выполнения рекурсивной функции можно представить в виде дерева.

  • Та же логика может быть реализована циклом, который использует структуру данных для обхода этого дерева.

  • Обход в глубину можно выполнить с помощью стека, обойти в ширину можно с помощью очереди.

Итак, ответ: да. Почему: https://stackoverflow.com/a/531721/2128327.

Может ли какая-либо рекурсия выполняться в одном цикле? Да, потому что

машина Тьюринга делает все, что делает, выполняя один цикл:

  1. получить инструкцию,
  2. оцените,
  3. Перейти к 1.
6 голосов
/ 02 ноября 2009

Да, всегда можно написать нерекурсивную версию. Тривиальным решением является использование структуры данных стека и моделирование рекурсивного выполнения.

6 голосов
/ 31 мая 2009

Да, используя явно стек (но рекурсия гораздо приятнее читать, ИМХО).

3 голосов
/ 08 июля 2009

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

Учитывая реальный язык программирования, ответ не так очевиден. Проблема в том, что вполне возможно иметь язык, в котором объем памяти, который может быть выделен в программе, ограничен, а объем стека вызовов, который можно использовать, не ограничен (32-битный C, где адрес переменных стека не доступно). В этом случае рекурсия является более мощной просто потому, что она имеет больше памяти, которую она может использовать; недостаточно явно выделяемой памяти для эмуляции стека вызовов. Для подробного обсуждения этого см. это обсуждение .

1 голос
/ 31 мая 2009

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

Теперь это не проблема, поскольку мода перешла на другие технологии.

1 голос
/ 21 мая 2013

Все вычисляемые функции могут быть вычислены с помощью машин Тьюринга, и, следовательно, рекурсивные системы и машины Тьюринга (итерационные системы) эквивалентны.

...