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

Тема 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))

19 ответов

Решение

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

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

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

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

Я вижу одну вескую причину. Предположим, у вас есть прототип системы на языке сверхвысокого уровня, например 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 и, вероятно, очень уродливо и неэффективно.

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

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

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

Итак, ответ: да. Почему: /questions/28603373/kakie-rekursivnyie-funktsii-nelzya-perepisat-s-pomoschyu-tsiklov/28603382#28603382.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Имея это в виду, почти все остальное, что вы говорите, это чепуха. Единственное, что вы говорите, не является чепухой, это идея, что вы не можете представить программирование без стека вызовов. Это то, что делалось десятилетиями, пока использование callstack не стало популярным. В старых версиях 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

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

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

Более того, я не вижу, как КТ демонстрирует, что все рекурсивные алгоритмы могут стать итеративными. Мне только кажется, что "все", обладающее "мощью" машины Тьюринга, может выражать все алгоритмы, которые это может выразить. Если машина Тьюринга не может рекурсии, мы уверены, что у каждого рекурсивного алгоритма есть свой интерактивный перевод... Машина Тьюринга может рекурсии? По моему мнению, если это можно "реализовать" (любым способом), то можно сказать, что оно есть. Есть это? Я не знаю.

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

Избегая копирования (1) и "имитированного стека"(2), мы продемонстрировали, что каждый рекурсивный алгоритм на реальных машинах может быть выражен итеративно?! Я не вижу, где мы это продемонстрировали.

Другие вопросы по тегам