It is a basic fact of set theory that the following holds:


Let $(X,\leq)$ be a linear ordered set. Then it holds that, for each finite sequence $y\_{1}$,...,$y\_{n}$ of sets and each formula $\phi(x,y\_{1},...,y\_{n})$ of set theory, we have


$$\forall{y\_{1},...,y\_{n}}(\forall{x\in X}(\forall{z}\lt x\phi(z,y\_{1},...,y\_{n})\rightarrow\phi(x,y\_{1},...,y\_{n}))\rightarrow\forall{x\in X}\phi(x,y\_{1},...,y\_{n}))$$


iff $(X,\leq)$ is a well-ordering. Hence induction works on $(X,\leq)$ iff $(X,\leq)$ is a well-ordering.


We can ask the same question for the recursion principle:


Let $(X,\leq)$ be a linear ordering such that, for each function $F:V\times V\times V\rightarrow V$, and each parameter $p$, there is a unique function $f:X\rightarrow V$ such that $f(x)=F(x,f|X\_{x},p)$ for all $x\in X$, where 
$X\_{x}$ is the subset of $X$ consisting of all elements strictly smaller than $x$ 
and $f|A$ is the restriction of $f$ to $A$.


Does it then follow that $(X,\leq)$ is a well-ordering?


This is obviously true if we assume the axiom of foundation. E.g. we could otherwise use 
$F(x,y)=y$ to construct an ill-founded set.


However, the first fact about induction seems to be more 'logical' in nature and does not depend on the axiom of foundation. I would therefore be interested in knowing whether the second fact can also be deduced without assuming foundation.



"Ill-founded Recursion" without Fund
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$. 


