Избыточные решения. При построении программ на Прологе следует обратить внимание на важную характеристику программы, не имеющую аналогов в логическом программировании отсутствие избыточных решений.
Значением логической программы является множество выводимых из программы основных целей. Здесь не существенно, выводится ли цель единственным образом или существует несколько различных выводов однако это существенно в Прологе, поскольку от этого зависит эффективность поиска решений. Каждый возможный вывод означает дополнительную ветвь в дереве поиска. чем больше дерево поиска, тем дольше продолжается вычисление. В общем случае желательно сохранить размер дерева поиска по возможности минимальным.
Наличие избыточных решений из-за возвратов может вызвать в предельном случае экспоненциальный рост времени работы программы. При решении конъюнкции n целей, каждая из которых имеет одно избыточное решение, в случае возвратов может быть порождено 2n решений, что приводит к изменению оценки времени работы программы от полиноминальной или даже линейной к экспоненциальной. Одна из причин появления избыточных решений в программах на Прологе состоит в наличии различных правил, пригодных для одного и того же случая. Другая причина, приводящая к избыточным решениям, состоит в рассмотрении слишком большого числа специальных случаев.
Иногда подобное рассмотрение мотивируется стремлением к эффективности. Для исключения избыточных решений можно добавить дополнительный факт, что позволит сократить рекурсивные вычисления, когда существует аргумент пустой список. Каждое предложение должно применяться лишь к спискам с ненулевым вторым аргументом. 2.4.