In particular, how much memory does a recurrent NN require as a function of the dataset size,number of nodes, etc., and how expensive is it to evaluate at runtime given a new test point?
I've found some time ago two interesting papers about recurrent neural networks and their complexity. I guess you can use those as a reference points at least:
Besides the excellent references given by
sebap123, from the Deep Learning Book by Ian Goodfellow et.al,
The recurrent neural network [given] is universal in the sense that any function computable by a Turing machine can be computed by such a recurrent network of a finite size. The output can be read from the RNN after a number of time steps that is asymptotically linear in the number of time steps used by the Turing machine and asymptotically linear in the length of the input .
Hope this helps!