Каждая рекурсия может быть преобразована в повторение?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• HALT ,

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

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

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

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