Должен ли я избегать рекурсии хвоста в Прологе и вообще?

Ответ 1

Короткий ответ: рекурсия хвоста желательна, но не переоценивайте ее.

Ваша исходная программа как хвост рекурсивна, как вы можете получить в Prolog. Но есть более важные проблемы: правильность и завершение.

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

Но ваша попытка оптимизации имеет определенный смысл. По крайней мере, с исторической точки зрения.

Еще в 1970-х годах основным языком ИИ был LISP. И соответствующее определение было бы

(defun addone (xs)
  (cond ((null xs) nil)
    (t (cons (+ 1 (car xs))
         (addone (cdr xs))))))

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

В Prolog, однако, вы можете создать минусы, чтобы знать фактические значения, благодаря логическим переменным. Так много программ, которые не были хвостовыми рекурсивными в LISP, переведены на хвостовые рекурсивные программы в Prolog.

Последствия этого все еще можно найти во многих учебниках Prolog.

Ответ 2

Ваша процедура addOne уже рекурсивна.

Нет точек выбора между головкой и последним рекурсивным вызовом, потому что /2 является детерминированным.

Аккумуляторы когда-то добавляются, чтобы разрешить рекурсию хвоста, более простой пример, о котором я могу думать, - обратное /2. Вот наивный обратный (nreverse/2), не хвостовой рекурсивный

nreverse([], []).
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R).

если мы добавим аккумулятор

reverse(L, R) :- reverse(L, [], R).
reverse([], R, R).
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R).

теперь reverse/3 является хвостовым рекурсивным: рекурсивный вызов является последним, и не остается никакой точки выбора.

Ответ 3

O.P. сказал:

Но я прочитал, что лучше избегать рекурсии [tail] по соображениям производительности. Это правда? Считается ли "хорошей практикой" всегда использовать рекурсию хвоста? Будет ли он стоить усилий, чтобы использовать аккумуляторы, чтобы получить хорошую привычку?

Это довольно простая оптимизация для преобразования хвостовой рекурсивной конструкции в итерацию (цикл). Поскольку хвостовой (рекурсивный) вызов является последним, кадр стека может быть повторно использован в рекурсивном вызове, что делает рекурсию для всех целей и целей циклом, просто переходя к началу предиката/функции/метода/подпрограмма. Таким образом, хвостовой рекурсивный предикат не будет переполнять стек. Хвост-рекурсивная конструкция с применяемой оптимизацией имеет следующие преимущества:

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

Возможные недостатки?

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

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

Процитировать Wikipedia:

Хвост звонков является значительным, поскольку они могут быть реализованы без добавления новый стек стека в стек вызовов. Большая часть кадра текущей процедуры больше не требуется, и его можно заменить рамкой хвостового вызова, (по аналогии с наложением для процессов, но для функции звонки). Затем программа может перейти к вызываемой подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранение хвостового вызова или хвост оптимизация вызовов.

См. также:

• Что такое оптимизация хвостового звонка?
• Репозиторий шаблонов Portland по этому вопросу
• и даже Microsoft MSDN

Я никогда не понимал, почему другие языки не реализуют оптимизацию хвостовой рекурсии

Ответ 4

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

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

Итак, как вы можете реализовать рабочую хвостовую рекурсивную версию addone? Это может быть обман, но если предположить, что reverse реализуется с хвостовой рекурсией (например, см. здесь), то он может быть использован для устранения вашей проблемы:

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],Acc,Result) :- reverse(Acc, Result).
addone(List,Result) :- accAddOne(List,[],Result).

Это, конечно, неуклюжий.: -)

Кстати, я не могу найти более простого решения. Это может быть по той же причине, что и foldr в Haskell, как правило, не определяется с хвостовой рекурсией.