Different ways for stating the recursion theorem

Another answer has already explained why both versions are equivalent. However, I want to add that there is a third version that is actually preferable if you want to be able to use the recursion theorem easily.

3. Given any set $X$ and function $R∈F→F$ where $F = { g : k∈ω ∧ g∈k→X }$, there is a function $h∈ω→X$ such that $h(k) = F(h↾k)$ for every $k∈ω$.

This version allows you to define the value of the recursive function $h$ on an input $k$ based on not just $k$ but also all the values of the recursive function on inputs less than $k$, since this information can all be obtained from $h↾k$. (In case you are not familiar with $ω$, treat it as the naturals such that $k = { j : j∈ω ∧ j<k }$ for every $k∈ω$.)

You should be able to see how version (2) can be used to prove version (3), by applying it to $R$ and then taking the union.

~ ~ ~

I also want to point out a significantly stronger version of the recursion theorem:

3. Given any object $c$ and a 2-parameter predicate $Q$ such that $∀x ∃!y ( Q(x,y) )$, there is a function $h$ with domain $ω$ such that $h(0) = c$ and $Q(h(k),h(k^+))$ for every $k∈ω$.

This version cannot be proven without using the replacement schema in ZFC, because it can be used to construct $V_{ω+ω}$, which is a model of ZFC minus replacement. Replacement also does not immediately furnish a suitable codomain for the desired $h$, since the "$∀x$" in "$∀x ∃!y ( Q(x,y) )$" is an unbounded quantifier. So to prove (3) we need to do something else. One easy way is to prove $∀k{∈}ω ∃!g ( FD(g,k^+) ∧ g(0)=c ∧ ∀j{∈}k ( Q(g(j),g(j^+)) ) )$ where $FD(g,d)$ is a predicate that says "$g$ is a function with domain $d$", which would require using the well-ordering of $ω$, and then use replacement to get $∃F ∀k{∈}ω ∃!g{∈}F ( FD(g,k^+) ∧ g(0)=c ∧ ∀j{∈}k ( Q(g(j),g(j^+)) ) )$, and finally construct $h = bigcup { g : g∈F ∧ k∈ω ∧ FD(g,k^+) ∧ g(0)=c ∧ ∀j{∈}k ( Q(g(j),g(j^+)) ) }$ and prove that $h$ is a function witnessing the claim.

At first glance, it seems that the first variant is more general (to compute the next term, you can use the previous term - but also the current index). More formally, if the first version holds and you are given $X,a,f$ as in the second, then apply the first to $A:=X$, $r(n,a):=f(a)$. Then the $f$ (in the notation of 1) is a valid $u$ (in the notation of 2).

Interestingly, however, we can also infer the first variant from the second: Assume we are given $A,a,r$ as in the first. Let $X=Ntimes A$ and define $fcolon Xto X$ as $f(langle n,arangle) = langle n^+,r(n,a)rangle$. Then the existing $u$, composed with the projection $Ntimes Ato A$ is a valid solution for the first variant.