Существуют ли проблемы, которые невозможно записать с помощью хвостовой рекурсии?

Рекурсия хвоста является важной функцией оптимизации производительности в функциональных языках, поскольку она позволяет рекурсивным вызовам потреблять постоянный стек (а не O (n)).

Существуют ли какие-либо проблемы, которые просто не могут быть записаны в хвосто-рекурсивном стиле или всегда можно преобразовать наивно-рекурсивную функцию в хвосто-рекурсивную?

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

Да, на самом деле вы можете взять код и преобразовать каждый вызов функции – и каждый возврат – в хвостовой вызов. То, что вы в конечном итоге, называется продолжением, проходящим стиль, или CPS.

Например, вот функция, содержащая два рекурсивных вызова:

(define (count-tree t) (if (pair? t) (+ (count-tree (car t)) (count-tree (cdr t))) 1)) 

И вот как это выглядело бы, если бы вы преобразовали эту функцию в стиль продолжения прохождения:

 (define (count-tree-cps t ctn) (if (pair? t) (count-tree-cps (car t) (lambda (L) (count-tree-cps (cdr t) (lambda (R) (ctn (+ LR)))))) (ctn 1))) 

Дополнительный аргумент, ctn , – это процедура, которая вызывает tail- count-tree-cps tail-calls вместо возврата . (Ответ sdcvvc говорит, что вы не можете делать все в O (1) пространстве, и это правильно, здесь каждое продолжение – это замыкание, которое занимает некоторую память.)

Я не преобразовал вызовы на car или cdr или + в хвостовые звонки. Это тоже можно было бы сделать, но я предполагаю, что эти листовые звонки действительно будут встроены.

Теперь для забавной части. Chicken Scheme действительно делает это преобразование во всем компилируемом коде. Процедуры, составленные Куриной, никогда не возвращаются . Существует classическая статья, объясняющая, почему Chicken Scheme делает это, написанное в 1994 году до того, как Chicken был реализован: CONS не должен противоречить его аргументам. Часть II: Чейни на MTA

Удивительно, но стиль продолжения прохождения довольно распространен в JavaScript. Вы можете использовать его для выполнения длительных вычислений , избегая всплывающего windows «медленного сценария» браузера. И это привлекательно для асинхронных API. jQuery.get (простая shell вокруг XMLHttpRequest) явно находится в стиле продолжения прохождения; последний аргумент – это функция.

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

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

Вот пример функции, которая является «рекурсивной» (на самом деле это просто итерация), но не хвостовой рекурсивной:

 factorial n = if n == 0 then 1 else n * factorial (n-1) 

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

 factorial n = fn 1 where fn product = if n == 0 then product else f (n-1) (n * product) 

Внутренняя функция f является хвостовой рекурсивной и компилируется в замкнутый цикл.


Я считаю, что следующие различия полезны:

  • В итеративной или рекурсивной программе вы решаете проблему размера n , сначала разрешая одну подзадачу размера n-1 . Вычисление факторной функции относится к этой категории, и это можно сделать либо итеративно, либо рекурсивно. (Эта идея обобщает, например, функцию Фибоначчи, где вам нужны n-1 и n-2 для решения n .)

  • В рекурсивной программе вы решаете проблему размера n , сначала решая две подзадачи размером n/2 . Или, в более общем плане, вы решаете проблему размера n , сначала разрешая подзадачу размера k и один размер nk , где 1 < k < n . Quicksort и mergesort являются двумя примерами такого рода проблем, которые могут быть легко запрограммированы рекурсивно, но не так просто запрограммировать итеративно или использовать только рекурсию хвоста. (Вы, по сути, должны имитировать рекурсию, используя явный стек.)

  • В динамическом программировании вы решаете проблему размера n , сначала решая все подзадачи всех размеров k , где k . Нахождение кратчайшего маршрута из одной точки в другую в лондонском метро - пример такой проблемы. (Лондонский метрополитен - многосвязный граф, и вы решаете проблему, сначала найдя все точки, для которых кратчайший путь равен 1 остановке, а затем кратчайший путь - 2 остановки и т. Д.)

Только первый вид программы имеет простое преобразование в хвостовую рекурсивную форму.

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

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

Обратите внимание, что только потому, что что-то является хвостовым рекурсивным, это не означает, что его использование памяти является постоянным. Это просто означает, что стек обратного вызова не растет.

Вы не можете делать все в O (1) пространстве (теорема пространственной иерархии). Если вы настаиваете на использовании хвостовой рекурсии, вы можете сохранить стек вызовов как один из аргументов. Очевидно, это ничего не меняет; где-то внутри, есть стек вызовов, вы просто делаете его явно видимым.

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

Такое преобразование не уменьшит пространственную сложность.

Как прокомментировал Паскаль Куок, другим способом является использование CPS ; тогда все вызовы являются рекурсивными.

Я не думаю, что что-то вроде tak может быть реализовано с использованием только хвостовых вызовов. (не допускающие продолжения)

Давайте будем гением компьютера.