  We show that the problem of deciding whether in a multi-player perfect
information recursive game (i.e. a stochastic game with terminal rewards) there
exists a stationary Nash equilibrium ensuring each player a certain payoff is
Existential Theory of the Reals complete. Our result holds for acyclic games,
where a Nash equilibrium may be computed efficiently by backward induction, and
even for deterministic acyclic games with non-negative terminal rewards. We
further extend our results to the existence of Nash equilibria where a single
player is surely winning. Combining our result with known gadget games without
any stationary Nash equilibrium, we obtain that for cyclic games, just deciding
existence of any stationary Nash equilibrium is Existential Theory of the Reals
complete. This holds for reach-a-set games, stay-in-a-set games, and for
deterministic recursive games.
