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

Да, на самом деле вы можете взять некоторый код и преобразовать каждый вызов функции и каждый возврат в хвостовой вызов. То, что у вас получается, называется стилем продолжения передачи или 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 (+ L R))))))
    (ctn 1)))

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

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

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

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

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

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

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

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

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

factorial n = f n 1
   where f n 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 и подзадачу размера n-k, где 1 < k < n. Быстрая сортировка и сортировка слиянием - два примера такого рода проблем, которые можно легко запрограммировать рекурсивно, но не так просто программировать итеративно или с использованием только хвостовой рекурсии. (По сути, вам нужно смоделировать рекурсию, используя явный стек.)

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

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

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

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

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

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

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

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

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

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