Cycle detection
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function f that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values x 0 , x 1 = f ( x 0 ) , x 2 = f ( x 1 ) , … , x i = f ( x i − 1 ) , … {\displaystyle x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots } must eventually use the same value twice: there must be some pair of distinct indices i and j such that xi = xj.