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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. получить инструкции,
2. оценить его,
3. Гото 1.

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

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

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

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

Это меньше проблем теперь же мода сместилась в сторону других технологий.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

кстати, существуют полные языки Тьюринга, которые реализуют только рекурсию (например, 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).

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

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

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