Может ли каждая рекурсия быть преобразована в итерацию?

Reddit нить воспитал , видимо , интересный вопрос:

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

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

(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))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. получить инструкцию,
2. оценить это,
3. Перейти к 1.

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

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

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

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

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

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

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

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

Ниже приведены простые случаи:

• хвостовая рекурсия
• прямая линейная рекурсия

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

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

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

http://en.wikipedia.org/wiki/Trampoline_(computers)

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

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

• Рекурсия по информатике
• Рекуррентное отношение

Далее следует параграф, который может дать вам подсказку о том, с чего начать:

Решение рекуррентного отношения означает получение решения в замкнутой форме : нерекурсивной функции от n.

Также взгляните на последний абзац этой записи .

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

Более подробная информация: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

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

Имея это в виду, почти все остальное, что вы говорите, это чепуха. Единственное, что вы говорите, не является чепухой, это идея, что вы не можете представить программирование без стека вызовов. Это то, что делалось десятилетиями, пока использование стека вызовов не стало популярным. В старых версиях FORTRAN не было стека вызовов, и они работали просто отлично.

Между прочим, существуют языки, полные по Тьюрингу, которые реализуют только рекурсию (например, SML) как средство зацикливания. Существуют также языки, полные по Тьюрингу, которые реализуют итерацию только как средство зацикливания (например, FORTRAN IV). Тезис Черча-Тьюринга доказывает, что все, что возможно на рекурсивных языках, может быть сделано на нерекурсивном языке, и наоборот, благодаря тому, что они оба обладают свойством полноты по Тьюрингу.

Вот итерационный алгоритм:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end