Partial words are sequences over a finite alphabet that may contain wildcard
symbols, called holes, which match or are compatible with all letters; partial
words without holes are said to be full words (or simply words). Given an
infinite partial word w, the number of distinct full words over the alphabet
that are compatible with factors of w of length n, called subwords of w, refers
to a measure of complexity of infinite partial words so-called subword
complexity. This measure is of particular interest because we can construct
partial words with subword complexities not achievable by full words. In this
paper, we consider the notion of recurrence over infinite partial words, that
is, we study whether all of the finite subwords of a given infinite partial
word appear infinitely often, and we establish connections between subword
complexity and recurrence in this more general framework.