Define $F(x,f,p)$ to be the smallest ordinal not in the range of $f$ (so the variables $x$ and $p$ are just dummy variables, to match the notation in the question). Suppose there exists a solution $f$ of the recursion $f(x)=F(x,f|X_x,p)$. Then $f$ embeds $X$ (with its given ordering) strictly monotonically into the ordinals (with their standard well-ordering). It follows that the given ordering of $X$ is a well-ordering.

Define $F(x,f,p)$ to be the smallest ordinal not in the range of $f$ (so the variables $x$ and $p$ are just dummy variables, to match the notation in the question). Suppose there exists a solution $f$ of the recursion $f(x)=F(x,f|X_x,p)$. Then $f$ embeds $X$ (with its given ordering) strictly monotonically into the ordinals (with their standard well-ordering). It follows that the given ordering of $X$ is a well-ordering.

Addendum (the next day, without jet lag, I hope): The choiceless version of the proof from uniqueness isn't actually hard; it's very close to what Peter Komjáth wrote, but, for the record, here it is. Suppose $A$ is a nonempty subset of $X$; I must show that it has a smallest element. Define $F(x,f,p)$ to be 1 if $x\in A$ and some $y<x$ has $f(y)=1$, and to be 0 otherwise. Then the identically 0 function satisfies the recursion $f(x)=F(x,f|X_x,p)$. The function $g$ that is identically 1 on $A$ and 0 on $X-A$ is different from $f$ (as $A\neq\emptyset$) and therefore must not satisfy the recursion. If $x$ is a point where the recursion equation $g(x)=F(x,g|X_x,p)$ is violated, then $x\in A$ (otherwise the value $g(x)=0$ satisfies the recursion) and no element of $A$ is $<x$ (otherwise the value $g(x)=1$ satisfies the recursion). So $x$ is the smallest element of $A$.

Let me also mention another proof from existence, a proof that doesn't need ordinals and in fact uses only (recursive definitions of) functions with values in $\{0,1\}$. For nonempty $A\subseteq X$, define $F(x,f,p)$ to be 1 if $x\in A$ and no $y<x$ has $f(y)=1$, and to be 0 otherwise. Suppose $f$ satisfies this recursion. If it were identically zero, then the recursion equation would say that it should be 1 at points in $A$; since $A\neq\emptyset$, this is a contradiction. So $f(x)=1$ for some $x$. The recursion equation then requires that $x\in A$. Suppose, toward a contradiction, that $A$ had an element $x'<x$. By the recursion equation and the fact that $f(x)=1$, we know that $f(y)=0$ for all $y<x$, hence in particular for all $y<x'$. But then the recursion equation makes $f(x')=1$, which is absurd as $x'$ is one of the $y$'s that are $<x$ and are therefore mapped to 0 by $f$. This contradiction completes the proof that $x$ is the smallest element in $A$.