Essentially, for you to be able to give a function recursively the domain must be well-ordered. And it all depends on what you mean by "recursive mapping"; see below.
A partial oder $\preceq$ on a set $X$ is a well-order if and only if every nonempty subset of $X$ has a least element under the relation $\preceq$. Assuming the Axiom of Choice, every set can be well-ordered, but these well-orders may not be explicit or constructive.
The following is from Halmos's Naive Set Theory (Chapter 18: Transfinite Recursion):
If $(W,\preceq)$ is a well-ordered set, and $X$ is an arbitrary set, a sequence of type $a$ in $X$ means a function from the initial segment of $a$ in $W$, $\{w\in W\mid w\prec a\}$, to $X$.
A sequence function of type $W$ in $X$ is a function $f$ whose domain is all sequences of type $a$ in $X$, for all $a\in W$, and whose range is contained in $X$; essentially, a "sequence function" tells you how to lengthen a sequence.
Transfinite Recursion Theorem. If $(W,\preceq)$ is a well-ordered set, and if $f$ is a sequence function of type $W$ in a set $X$, then there exists a unique function $U\colon W\to X$ such that $U(a) = f(U|_{i(a)})$ for each $a\in W$, where $i(a)=\{ w\in W\mid w\prec a\}$ is the initial segment determined by $a$ in $W$.
The theorem tells you that you can define a function recursively on a well-ordered set (with a given well order).
Now, when can a function be defined recursively? In a sense, always if your domain is well-ordered. To see why, consider the case of $\mathbb{N}$ first.
Suppose you have an arbitrary function $f\colon\mathbb{N}\to X$. Let $g\colon \mathbb{N}\times X\to X$ be a function defined as follows: fix $x_0\in X$; then $g(n,x) = \left\{\begin{array}{ll} f(n+1) &\text{if $f(n)=x$;}\\ x_0 &\text{if $f(n)\neq x$.} \end{array}\right.$ Then we have $f(n+1) = g(n,f(n))$, so that $f$ is defined "recursively". This can be done with any function, so every function with domain $\mathbb{N}$ can be defined "recursively" this way.
Similar constructions hold for an arbitrary well-ordered set.
You might say, "but you're cheating! you start with $f$ and you determine $g$ from it". Well, yes; but if you were walking on the street and you found $g$ lying on the corner, and didn't know where it came from, you would still be able to use it to define a function. This tells you that there is always a way of writing $f$ recursively, even if it is a bit silly in the grand scheme of things. The problem is that we have no good way of distinguishing "silly ways" and "real ways", other than the way that Justice Potter Stewart was able to tell what was and what was not pornography: we know it when we see it.