Снова о хвостовой рекурсии

Является ли add1 (добавление 1) хвостовой рекурсией? Если вы знакомы

с Лиспом или Паскалем, то можете подумать, что нет, т.к. считаете, что

предикат выполняет следующие операции:

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 уже являются головой и

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

образом рекурсивный вызов является последним шагом.