Recurrent neural networks are good at solving prediction problems. However, finding a network that suits a problem is quite hard because their performance is strongly affected by their architecture configuration. Automatic architecture optimization methods help to find the most suitable design, but they are not extensively adopted because of their high computational cost. In this work, we introduce the Random Error Sampling-based Neuroevolution (RESN), an evolutionary algorithm that uses the mean absolute error random sampling, a training-free approach to predict the expected performance of an artificial neural network, to optimize the architecture of a network. We empirically validate our proposal on four prediction problems, and compare our technique to training-based architecture optimization techniques, neuroevolutionary approaches, and expert designed solutions. Our findings show that we can achieve state-of-the-art error performance and that we reduce by half the time needed to perform the optimization.