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

Question

А ветка на реддите поднял, видимо, интересный вопрос:

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

(Встречный?) Пример в посте - это пара:

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

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

Answer 9

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

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

Answer 10

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

Answer 11

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

Следующие случаи относятся к числу простых:

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

Answer 12

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

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

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

http://en.wikipedia.org/wiki/Trampoline_(компьютеры)

Answer 13

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

Answer 14

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

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

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

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

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

Answer 15

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

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

Answer 16

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

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

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

Answer 17

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

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