Во многих задачах из различных областей знания ставятся вопросы-задания типа: “Сколько существует способов …”, “Подсчитайте количество элементов …”, “Перечислите все возможные варианты …”, “Есть ли способ …”, “Существует ли объект…” и т. п. Ответы на них, как правило, требуют исчерпывающего поиска в некотором множестве M всех возможных вариантов, среди которых находятся решения конкретной задачи. Существуют два общих метода организации исчерпывающего поиска: перебор с возвратом (backtracking) и его естественное логическое дополнение - метод решета.

Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отметать как можно раньше и как можно больше заведомо неподходящих вариантов M. Незначительные модификации метода перебора с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ (branch and bound), поиск в глубину (depth first search), метод проб и ошибок и т. д. Перебор с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания. Он находит применение при решении различных комбинаторных задач в области искусственного интеллекта.

При использовании метода решета вместо конструктивного построения решений задачи из множества возможных вариантов M исключаются все элементы, не являющиеся решениями. Методы решета нашли широкое применение в теоретико-числовых задачах.

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

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

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