Алгоритм двоичного поиска похож на алгоритм последовательного поиска, так как каждый из них предусматривает выполнение повторяющегося процесса. Однако реализация этого повторения в каждом случае существенно отличается. При последовательном поиске повторение организуется с помощью цикла, в случае двоичного поиска каждая стадия повторения реализуется как подзадача предыдущей стадии. Этот метод повторения известен как рекурсия (recursion).
При выполнении рекурсивного алгоритма создается иллюзия существования множества его копий, называемых активациями (activation), которые появляются и исчезают по мере выполнения алгоритма. Из всех активаций, существующих в заданный момент времени, активно функционирует только одна. Все остальные фактически остановлены, поскольку каждая из них ожидает, пока завершится следующая, запущенная ею активация, и только после этого она сможет продолжить свою работу.
Будучи повторяющимися процессами, рекурсивные структуры почти так же зависят от корректного управления, как и циклические структуры. Как и в случае управления циклами, рекурсивные системы зависят от проверки условия окончания и должны разрабатываться так, чтобы иметь гарантии, что это условие будет обязательно выполнено. Фактически правильно организованное управление рекурсией включает те же три операции, что и управление циклом, — инициализация, модификация и проверка условия окончания.
