Могут ли все итерационные алгоритмы быть выражены рекурсивно?

Question

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

Если это так, что все итерационные алгоритмы могут быть выражены рекурсивно, существуют ли случаи, когда это сделать труднее?

Кроме того, какую роль играет язык программирования во всем этом? Я могу себе представить, что у программистов на Scheme итерация (= tail-recursion) и использование стека иные, чем у программистов только на Java.

Answer 1

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

Answer 2

Можно ли рекурсивно выразить все итерационные алгоритмы?

Да, но доказательство не интересно:

1. Преобразовать программу со всеми еепоток управления в один цикл, содержащий одну инструкцию case, в которой каждая ветвь является линейным потоком управления, возможно, включающим break, return, exit, raise и так далее.Введите новую переменную (назовите ее «счетчик программы»), которую оператор case использует, чтобы решить, какой блок выполнять следующим.

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

2. Замените цикл рекурсивной функцией и замените каждую изменяемую локальную переменную параметром этой функции.Вуаля!Итерация заменена на рекурсию.

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

Answer 3

Как вы говорите, каждый итеративный подход можно превратить в "рекурсивный", и при использовании хвостовых вызовов стек также не взорвется.:-) На самом деле, именно так Scheme реализует все распространенные формы зацикливания.Пример на схеме:

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

Здесь, хотя функция выглядит итеративной, она фактически повторяется на внутренней лямбде, которая принимает три параметра x, y и i и вызывает себя сновые значения на каждой итерации.

Вот один способ, которым функция может быть расширена макросом:

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

Таким образом, рекурсивная природа становится более наглядной.

Answer 4

Определение итерационного как:

function q(vars):
  while X:
    do Y

Можно перевести как:

 function q(vars):
    if X:
      do Y
      call q(vars)

Y в большинстве случаев будет включать увеличение счетчика, который проверяется X. Эта переменная должна быть каким-то образом передана в 'vars' при прохождении рекурсивного маршрута.

Answer 5

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

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

Answer 6

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

Answer 7

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