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

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

(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)))

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

Определение итеративных как:

function q(vars):
  while X:
    do Y

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

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

y в большинстве случаев будет включать в себя увеличение счетчика, который проверяется X. Эта переменная должна быть передана в «Vars» в некотором роде. рекурсивный маршрут.

Вот быстрая сортировка:

def qsort (list):
    if (len(list) > 1):
        list = qsort(filter (lambda x: x <= list[0], list[1:])) + [list[0]] + qsort(filter (lambda x: x > list[0],  list[1:]))
    return list

Это решение программного головоломки поиска недостающего числа среди целых чисел от 1 до 100:

from random import randint
nos = range(1,101)
to_remove = randint(1,100)
nos.remove(to_remove)
print "Removed %d from list" % to_remove

found = 5050 - reduce (lambda x,y: x+y, nos)
print "You removed %d " % found

Почему бы jsut не использовать PHP-синтаксический анализатор?

 $terms=array('and','or','not','A','B','C','D'...);
 $values=array('*','+','!',1,1,0,0,1....);

 $expression="A and B or C and (D or F or not G)";
 $expression=preg_replace($terms, $values,$expression);
 $expression=preg_replace('^(+|-|!|1|0)','',$expression);
 $result=eval($expression);

На самом деле, что 2-й regex ошибочен (и требуется только если вам нужно предотвратить любую инъекцию кода) - но вы

C.

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

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

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

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

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

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

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

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