This paper is a first step in the study of the recurrence behavior in random dynamical systems and randomly perturbed dynamical systems. In particular we define a concept of quenched and annealed return times for systems generated by the composition of random maps. We moreover prove that for super-polynomially mixing systems, the random recurrence rate is equal to the local dimension of the stationary measure.