We analyze stability and recurrence of nonlinear stochastic discrete-time systems, also known as Markov control processes, under optimal control using discounted and undiscounted infinite-horizon cost functions. We make assumptions on cost-stabilizability as well as detectability with respect to the stage cost that apply to a range of stochastic systems. Furthermore, we assume regularity in the form of continuity of the model, stage cost and optimal value functions. Then, robust uniform semiglobal practical recurrence with respect to the discount factor is guaranteed. This property becomes global by strengthening the assumptions. In the case where policies with finite undiscounted infinite-horizon costs exist, the stronger property of uniform global asymptotic stability in probability holds under similar assumptions, as well as with discounting under extra conditions. Furthermore, since the continuity requirement of the optimal value function is not easily verified, we provide a novel sufficient condition in the form of strong continuity of the Markov kernel.