Нахождение цикла — алгоритмическая задача поиска цикла в последовательности значений итеративной функции[англ.].
Для любой функции f, отображающей конечное множество S в себя, и для любого начального значения x0 из S последовательность итеративных значений функции:
должна в конечном счёте использовать одно значение дважды, то есть должна существовать такая пара индексов i и j, что xi = xj. Как только это случится, последовательность будет продолжаться периодически, повторяя ту же самую последовательность значений от xi до xj − 1. Нахождение цикла — это задача поиска индексов i и j при заданной функции f и начальном значении x0.
Известно несколько алгоритмов поиска цикла быстро и при малой памяти. Алгоритм «черепахи и зайца» Флойда передвигает два указателя с различной скоростью через последовательность значений, пока не получит одинаковые значения. Другой алгоритм, алгоритм Брента, основан на идее экспоненциального поиска[англ.]. Оба алгоритма, Флойда и Брента, используют только фиксированное число ячеек памяти, и число вычислений функции пропорционально расстоянию от стартовой точки до первой точки повторения. Некоторые другие алгоритмы используют большее количество памяти, чтобы получить меньшее число вычислений значений функции.
Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах вычислительной теории чисел[англ.], для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического анализа формы[англ.] связных списков.
Рисунок показывает функцию f, отображающую множество S = {0,1,2,3,4,5,6,7,8} на себя. Если начать с точки x0 = 2 и повторять применение функции f к получаемым значениям, увидим последовательность значений