With the axiom of choice, this is trivial:

Let x in A

Let f(0) = x.

Let f(n+1) = the least member v of A such that vRf(n).

But also, it's very close to the axiom of dependent choice itself. Should poke around to see whether it is equivalent to the axiom of dependent choice.