Итерация может заменить рекурсию?

42

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

Была даже тема с сильным голосованием и ответом с большим количеством голосов : да, это возможно.

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

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

Я также сомневаюсь, что гипероперации могут быть выражены итеративно.

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

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

У меня вопрос такой:

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

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

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

PPS: Если ответ «да», не могли бы вы, например, написать итерационную версию не примитивно-рекурсивной функции. Например, Аккерманн в ответ. Это поможет мне понять.

Тоби Алафин
источник
21
Все, что вы запускаете на процессоре, является итеративным. Вы можете написать его рекурсивно на языке более высокого порядка, но в любом случае он будет скомпилирован в набор итерационных инструкций ассемблера. Таким образом, в буквальном смысле, компилятор делает именно то, о чем вы спрашиваете, он преобразует всю вашу причудливую рекурсию в набор итерационных инструкций для процессора.
Давор
6
На низком уровне большинство из нас знает, что рекурсия равна итерации плюс стек. Не зависящая от контекста грамматика моделирует рекурсию, в то время как автоматы pushdown являются итеративными «программами» со стековой памятью.
Хендрик Янв
2
Просто отметив, что, как правило, лучше подождать не менее 24 часов, чтобы увидеть, появляются ли другие ответы. Откровенно говоря, принятый вопрос кажется мне слишком длинным и запутанным, и, похоже, намеренно усложняет вопросы больше, чем необходимо. Основной ответ на ваш вопрос: «стек, используемый для рекурсии, может быть явно реализован итеративным способом», и он не должен быть намного более сложным, чем этот. Соображения о том, является ли память неограниченной или нет, не вступают в игру, так как эта функция необходима в любом случае и для рекурсивных стеков.
AnoE
Реализовать эмулятор машины Тьюринга можно только с помощью итерации
Sarge Borsch
В классе сравнительных языков, который я взял давным-давно, нам пришлось написать функцию Аккермана на ассемблере, на фортране (не на современном фортране) и на рекурсивном языке по своему выбору. Так что да, это возможно на практике. И конечно, это возможно в теории. См., Например, вопрос, доказывающий, что машины Тьюринга и лямбда-исчисление эквивалентны .
Дэвид Хаммен

Ответы:

52

Можно заменить рекурсию итерацией плюс неограниченную память .

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

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

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

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

Теперь предположим, что вы хотите смоделировать рекурсивные вычисления с помощью компьютера. Методы выполнения рекурсивных функций хорошо известны: каждый вызов функции имеет часть памяти, называемую кадром стека . Важно отметить, что рекурсивные функции могут распространять информацию посредством нескольких вызовов, передавая переменные. С точки зрения реализации на компьютере это означает, что вызов функции может получить доступ к кадру стека (grand-) * родительского вызова.

Компьютер - это процессор - конечный автомат (с огромным количеством состояний, но мы здесь занимаемся теорией вычислений, поэтому все, что имеет значение, это то, что он конечен) - в сочетании с конечной памятью. Микропроцессор запускает один гигантский цикл while: «при включенном питании прочитайте инструкцию из памяти и выполните ее». (Реальные процессоры намного сложнее, но это не влияет на то, что они могут вычислить, только на то, насколько быстро и удобно они это делают.) Компьютер может выполнять рекурсивные функции только с помощью этого цикла while для обеспечения итерации, плюс механизм для доступ к памяти, в том числе возможность увеличения объема памяти по желанию.

Если вы ограничиваете рекурсию примитивной рекурсией, то вы можете ограничить итерацию ограниченной итерацией. То есть вместо использования циклов while с непредсказуемым временем выполнения вы можете использовать циклы for, в которых число итераций известно в начале цикла¹. Число итераций может быть неизвестно в начале программы: оно само может быть вычислено предыдущими циклами.

Я не собираюсь даже набрасывать здесь доказательство, но есть интуитивная связь между переходом от примитивной рекурсии к полной рекурсии и переходом от циклов for к циклам while: в обоих случаях это означает, что вы заранее не знаете, когда стоп. При полной рекурсии это делается с помощью оператора минимизации, который продолжается до тех пор, пока вы не найдете параметр, удовлетворяющий условию. С циклами while это выполняется путем продолжения работы до тех пор, пока условие цикла не будет выполнено.

¹ циклы в C-подобных языках могут выполнять неограниченную итерацию точно так же , как это принято, ограничивать их ограниченной итерацией. Когда люди говорят о «для циклов» в теории вычислений, это означает только циклы, которые насчитывают от 1 до n (или эквивалент). forwhileN

Жиль "ТАК - перестань быть злым"
источник
Принимая для подробного объяснения, сохраняются на запрошенном уровне.
Тоби Алафин
12
Я думаю, что стоит отметить, что на реальных компьютерах рекурсия также использует память (растущий стек вызовов). Таким образом, в практических приложениях нет необходимости в неограниченной памяти (потому что все ограничено ею в равной степени). И рекурсии часто требуется больше памяти, чем итерации.
Agent_L
@Agent_L Да, рекурсии требуется неограниченная память, чтобы хранить все кадры стека. При рекурсивном подходе требуется неограниченная память, но она не может быть интуитивно отделена от последовательности операций, как с итерациями.
Жиль "ТАК ... перестать быть злым"
1
Возможно, интересным будет тезис Черча-Тьюринга. Машины Тьюринга - это итеративные машины без (присущих) концепций рекурсии. Лямбда-исчисление - это язык, разработанный для рекурсивного выражения вычислений. Тезис Черча-Тьюринга показал, что все лямбда-выражения можно оценивать на машине Тьюринга, связывая рекурсию и итерацию.
Cort Ammon
1
@BlackVegetable Если рекурсивный метод не имеет внутренних переменных и единственная память, которую он использует, это стек вызовов (что можно оптимизировать с помощью TCO), то его итерационная версия, скорее всего, также не будет иметь внутренних переменных и будет использовать только постоянный объем памяти ( переменные) распределяются между всеми итерациями, как счетчик.
Agent_L
33

Каждая рекурсия может быть преобразована в итерацию, о чем свидетельствует ваш процессор, который выполняет произвольные программы, используя бесконечную итерацию fetch-execute. Это форма теоремы Бёма-Якопини . Более того, многие модели вычислений, полные по Тьюрингу, не имеют рекурсии, например, машины Тьюринга и встречные машины .

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

Юваль Фильмус
источник
25

a(N,м)

s

От себя(s,Икс)ИксИкспоп(s)опорожнить(s)

Ackermann(N0,м0):

  • sзнак равно
  • От себя(s,N0)
  • От себя(s,м0)
  • в то время как (правда):
    • мпоп(s)
    • если(опорожнить(s)):
      • возвращение м
    • Nпоп(s)
    • если(Nзнак равно0):
      • От себя(s,м+1)
    • иначе если (мзнак равно0):
      • От себя(s,N-1)
      • От себя(s,1)
    • еще:
      • От себя(s,N-1)
      • От себя(s,N)
      • От себя(s,м-1)

Я реализовал это на Цейлоне, вы можете запустить его в WebIDE , если хотите. (Он выводит стек в начале каждой итерации цикла.)

Конечно, это просто переместило неявный стек вызовов из рекурсии в явный стек с параметрами и возвращаемыми значениями.

Пауло Эберманн
источник
16
Я думаю, что это важный момент. Вы совершенно ясно показали, что рекурсия не является чем-то особенным и что ее можно удалить, просто отслеживая стек вызовов самостоятельно, а не позволяя компилятору это делать. Рекурсия - это просто функция компилятора, которая облегчает написание такого рода программ.
Дэвид Ричерби
4
Спасибо, что приложили усилия, чтобы написать запрошенную программу.
Тоби Алафин
16

Уже есть несколько хороших ответов (с которыми я даже не могу надеяться конкурировать), но я бы хотел привести это простое объяснение.

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

Теперь, что произойдет, если вы создадите свой собственный стек, замените рекурсивные вызовы функций передачей в стек, замените возврат из рекурсивных функций выталкиванием стека и получите цикл while, который работал до тех пор, пока стек не опустел?

Александр - Восстановить Монику
источник
2

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

Луи Гиокас
источник