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

Question

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

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

The (? Счетчик) пример в посте пара:

(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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

случаях ниже являются одними из самых легко:

• хвостовая рекурсия
• direct linear recursion

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

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 

Answer 8

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

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

Answer 9

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

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

Answer 10

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

Answer 11

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

Answer 12

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

• Recursion in computer science
• Recurrence relation

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

Решая рекуррентное соотношение означает получение closed-form solution: а нерекурсивна функция n.

Также см. Последний абзац this entry.

Answer 13

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

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

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

программа

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

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

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

Answer 14

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

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

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

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

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

Answer 15

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

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

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

Answer 16

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

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

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

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

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

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

1. выборки инструкции,
2. оценить его,
3. Гото 1.

Answer 17

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

Answer 18

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

Подробнее: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions