Программа (в Prolog-псевдокоде):
(\text{append}([] , L, L).)
(\text{append}([H|T], L, [H|R]) :- \text{append}(T, L, R).)

Запрос: (\text{append}(X,Y,[1,2,3])).

Первые ответы (последовательные решения, получаемые при backtracking):
1) ({X = [],\; Y = [1,2,3]})
2) ({X = [1],\; Y = [2,3]})
3) ({X = [1,2],\; Y = [3]})
4) ({X = [1,2,3],\; Y = []})
далее решений нет.

Краткая демонстрация механизма (SLD-разрешение, шаги) — получение второго ответа:

Цель: (\text{append}(X,Y,[1,2,3])).Есть два сопоставимых правила: база (\text{append}([] , L, L)) и рекурсивное (\text{append}([H|T],L,[H|R])\dots). При первом совпадении Prolog выдаёт первое решение, но сохраняет choice point для второй клаузы.На backtracking выбирается вторая клауза и происходит унификация:
(X = [H|T]), (Y = L), ([H|R] = [1,2,3]) → (H = 1,\; R = [2,3]). Значит пока (X = [1|T]), (Y = L).Порождена рекурсивная подцель: (\text{append}(T, L, [2,3])).Эта подцель может унифицироваться с базой: (T = [],\; L = [2,3]). Тогда (X = [1|[]] = [1]), (Y = [2,3]) — второй ответ.

Механизм унификации:

Унификация сопоставляет структуру и, при необходимости, связывает переменные. Пример: ([H|R] = [1,2,3]) даёт (H=1,\; R=[2,3]).В стандартной Prolog-реализации нет occurs‑check: попытка унифицировать (X) с ([X|T]) не будет предотвращена и может породить цикличесное (рациональное) дерево.

Choice points и backtracking:

Choice point создаётся когда для цели есть несколько подходящих правил (или при наличии альтернатив внутри тела). Prolog запоминает место и текущие привязки переменных (через трассировку/трейл).При успехе Prolog возвращает решение; при запросе «;» или при последующем провале он откатывает изменения (undo) до последнего choice point и пытает следующий вариант.Каждая рекурсивная call может создавать свой набор choice points — это даёт все разбиения списка на префикс/suffix в нашем примере.

Типичные ловушки при проектировании рекурсивных предикатов:

Неправильный порядок целей: если рекурсивный вызов стоит до целей, которые сужают переменные, можно получить бесконечную рекурсию. Всегда думайте о том, какие переменные должны быть уже инстанциированы.Отсутствие корректного базового случая → бесконечная рекурсия/неудача.Отсутствие occurs‑check (стандартный Prolog) — риск циклических структур и неожиданных результатов.Неэффективные конструкции: частое использование (\text{append}) для наращивания справа приводит к квадратичной сложности; лучше использовать аккумулятор (хвостовую рекурсию) или difference lists.Неправильное или излишнее использование cut ((!)) ломает логическое поведение и может скрыть ошибки.Оставлять лишние choice points (недетерминированность) — приводит к росту поиска и снижению производительности.

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