In Reinforcement Learning (which is the domain I guess this question wants to look at) we are given a Markov decision automata (that very precisely spoken gives rise to infinitely many Markov Decision Processes that consist of random variables $A_t, S_t, R_t$) and we seek models $\pi$, i.e. functions $\pi:A \times S \to[0,1]$ that provide a 'good' distribution
$$p(a_t|s_t) = \pi(a_t|s_t)$$
such that a certain quantity (namely the infinite exponential sum over rewards) is being maximizes, i.e. we are looking for things that help us make decisions which action $a_t$ to take next given that we are currently in a state $s_t$ such that the long term reward is maximal.
I do not completely agree with @ReneBT: models such as RNNs can be seen as providing such a distribution over the action space given the past states, i.e. what they actually spit out is just numbers $y_{a}$ such that $\sum_{a} y_{a} = 1$ (the last layer is a softmax over the actions so that the probabilities of the actions sum up to one). The RNN itself does not really make a final decision on which action actually to use next (some people sample that from the action space according to this distribution, some people just take argmax, ...).
The question is: What does this distribution actually depend on? Technically, each call of the RNN unit receives the current input (state) $s_t$ and the hidden output of the call before $h_{t-1}$. However, the hidden state $h_{t-1}$ depends on $h_{t-2}$ and $s_{t-1}$ and so forth...
Hence, what they actually model is something like
$$p(a_t|s_t, s_{t-1}, s_{t-2}, ...)$$
and that is explicitly not Markovian because it depends on all the history instead of just the current and/or the current and the last state.
One should also remark that one can 'fix' models that only depend on a fixed past of states, i.e. if it looks like this
$$p(a_t|s_t, s_{t-1}, s_{t-2})$$
then one can reinterpret the state space as $S \times S \times S$ and then these models 'kinda' become Markovian (however, not in the original space!). As RNNs, however, depend on all the past $s_{t-1}, s_{t-2}, ..., s_0$ they cannot be fixed in that way. Theoretically they should be much stronger than Markovian models. However, from a purely theoretical point of view we do not really need these 'strong' models: Given that the state and action space satisfy some 'regularity conditions' (for example, they are both finite) then the best policy is a Markovian deterministic one (see Puterman: Markov Decision Processes and Discrete Stochastic Dynamic Programming, Thm. 6.2.10 on p. 154).
That is (I believe) the reason that everything is 'fair' again: We use something that is more powerful (i.e. we kinda cheat the setup) but we do not actually need to use it... It is just a helping tool in order to come closer to this -provably- best, discrete policy (in the same way that we are using probabilistic policies although we do only need to search through the space of deterministic ones... but this space is too big so we approximize by probabilistic ones).