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

Ответ 1

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

Ответ 2

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

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

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

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

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

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

Ответ 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)))

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

Ответ 4

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

function q(vars):
  while X:
    do Y

Может быть переведен как:

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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