In this paper, we generalize the bipolar recurrent correlation neural networks (RCNNs) of Chiueh and Goodman for patterns whose components are in the complex unit circle. The novel networks, referred to as complex-valued RCNNs (CV-RCNNs), are characterized by a possible nonlinear function, which is applied on the real part of the scalar product of the current state and the original patterns. We show that the CV-RCNNs always converge to a stationary state. Thus, they have potential application as associative memories. In this context, we provide sufficient conditions for the retrieval of a memorized vector. Furthermore, computational experiments concerning the reconstruction of corrupted grayscale images reveal that certain CV-RCNNs exhibit an excellent noise tolerance.