An S-necklace of length n is a circular arrangement of the integers 0, 1, 2, ..., n – 1 such that the absolute difference of two neighbors always belongs to S. Focusing in particular on the case |S| = 2, we prove that, subject to certain conditions on the two elements in S, the number of S-necklaces obeys a linear homogeneous recurrence relation. We give an algorithm for computing the corresponding generating function and compute generating functions and explicit recurrence relations for several small sets S. Our methods extend to sets S of any size.