We propose an explicit construction of a stationary solution for a stochastic recursion of the form X..=.(X) on a partially-ordered Polish space, when the monotonicity of . is not assumed. Under certain conditions, we show that an extension of the original probability space exists, on which a solution is well defined, and construct explicitly this extension using a randomized contraction technique. We then provide conditions for the existence of a solution on the original space. We finally apply these results to the stability study of two nonmonotonic queuing systems.