На этом шаге мы рассмотрим хвостовую рекурсию.

    Возможно, вы заметили, что length_of не является и не может быть хвостовой рекурсией потому, что рекурсивный вызов не является последним шагом в своем предложении. Можно ли написать предикат для определения длины списка, который будет хвостовой рекурсией? Да, но это потребует некоторых усилий.

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

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

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

    Рассмотрим пример.

   domains 
      list = integer* % или любой другой тип
   predicates
      length_of(list,integer, integer)
   clauses
      length_of([], Result, Result). 
      length_of([_|T],Result,Counter):-
         NewCounter=Counter + 1, 
         length_of(T, Result, NewCounter).
   goal
      length_of([1,2,3],L,0), % начать  со счетчика = 0
      write("L=",L),nl.

    Результат работы программы можно посмотреть на рис.1

Рис.1. Результат работы программы pro45_1.pro

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

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

   domains
      list = integer*
   predicates
      add1(list,list)
   clauses
      add1([], []). 
      add1([Head|Tail],[Head1|Tail1]):-% отделить голову списка
	Head1= Head+1,% добавить 1 к 1-му элементу		       
	add1(Tail,Tail1).% вызвать элемент из остатка списка 

    Переведя это на естественный язык, получим:

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

    Запустите программу с целевым утверждением

   add1([1,2,3,4],NewList)

   NewList=[2,3,4,5].
   1 решение

    Является ли add1 хвостовой рекурсией? Если вы знакомы с языками Лисп или Паскаль, то можете подумать, что нет, т. к. считаете, что предикат выполняет следующие операции:

1. Разделяет список на Head и Tail.
2. Добавляет 1 к Head и результат присваивает Head1.
3. Рекурсивно добавляет 1 ко всем элементам Tail, присваивает результат Tail1.
4. Объединяет Head1 и Tail1 и присваивает результат новому списку.

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

    Но, что важно - Пролог делает это не так; в нем add1 является хвостовой рекурсией, потому что шаги на самом деле следующие:

1. Связать голову и хвост исходного списка с Head и Tail.
2. Связать голову и хвост результата с Head1 и Tail1 (Head1 и Tail1 пока не определены).
3. Добавить 1 к Head и присвоить результат Head1.
4. Рекурсивно добавить 1 ко всем элементам Tail, присваивая результат Tail1.

    Когда все будет завершено, Head1 и Tail1 уже являются головой и хвостом результата, и нет отдельной операции для их объединения. Таким образом, рекурсивный вызов является последним шагом.

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

   domains
      list=integer*
   predicates
      discard_negatives(list,list)
   clauses
      discard_negatives([], []).
      discard_negatives([H |T],ProcessedTail):-
         H<0, % если Н отрицательно, то пропустить
         !,
         discard_negatives(T, ProcessedTail). 
      discard_negatives([H| T],[H |ProcessedTail]):-
        discard_negatives(T, ProcessedTail).

    К примеру, целевое утверждение

   discard_negatives([2,-45,3,468], X) 

   X = [2,3,468].

   doubletalk([ ],[ ]).
   doubletalk([H |T],[H,H |DoubledTail]):-
      doubletalk(T,DoubledTail).

    На следующем шаге мы рассмотрим принадлежность к списку.

Предыдущий шаг Содержание Следующий шаг