Рекурсия с итерацией

Question

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

Answer 1

Да, рекурсия всегда может заменить итерацию, это обсуждалось before. Цитата из связанного сообщения:

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

Пояснение немного: мы знаем, что любая вычислимая проблема может быть решена машиной Тьюринга. И можно построить язык программирования A без рекурсии, что эквивалентно машине Тьюринга. Аналогичным образом, можно построить язык программирования B без итерации, равный вычислительной мощности машине Тьюринга.

Следовательно, если оба A и B равны Turing-complete, мы можем заключить, что для любой итеративной программы должна существовать эквивалентная рекурсивная программа, и наоборот. Это теоретический результат в том смысле, что он не дает вам никаких намеков на то, как вывести одну рекурсивную программу из произвольной итеративной программы или наоборот.

Answer 2

Да. Существует тип рекурсии, называемый tail recursion, который напрямую переводится на итерацию. Без проблем можно преобразовать в другую. Таким образом, все итерационные решения могут быть преобразованы в рекурсивные решения.

На самом деле многие компиляторы могут обнаружить, что вы выполняете хвостовую рекурсию, а затем преобразуете ее в код типа for-loop для повышения эффективности.

Answer 3

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