# Need help understanding the Recursion Theorem (Set Theory)

I'm reading through Introduction to Set Theory by Jech and Hrbacek (3rd edition). I am going through the section on recursion theorem, and I am stuck on two things:

1. I usually see the theorem presented in this way:

Recursion Theorem: Given a set $X$, an element $a$ of $X$ and a function $f:X\rightarrow X$, then there is a unique function $F:\mathbb{N}\rightarrow X$ such that

1) $F(0)=a$

2)$F(n+1)=f(F(n))$

My first question is, why do we need a second function $f$? If we want our sequence to be factorial, fibonacci, etc, where does this second function $f$ (which to me seems like it kind of came out of nowhere) come into play?

1. While the above form of the theorem is used in most books I have looked up, the main one I am using (Introduction to Set Theory, Jech & Hrbacek) uses the following form:

My next question is, why does the function in this case need to be from a product of sets into our original? How come this one uses the $n$ in the argument unlike the one above? Which one is "better"? Thanks in advance for any reponse.

In order to define a function $F$ by recursion, what we need is an initial condition ($F(0)$) together with a rule telling us how to figure out what $F(\alpha)$ should be if we know $F(\beta)$ for every $\beta<\alpha$. (Note the way I've phrased it here allows us to consider defining functions with domain an arbitrary ordinal, not just the natural numbers.)
This is what the "second" function - $f$ in your first version, and $g$ in your second version - is doing. The difference between the two versions is what sort of information we consider when defining subsequent values of $F$. In the first version, $F(n+1)$ is only allowed to depend on $F(n)$; in the second, it's allowed to take into account what $n$ is.
This latter approach is much broader and more natural. For instance, defining factorial via recursion in the second method is easy: let $g(x, y)=x(y+1)$. In the former, it's much more complicated to come up with the right $f$. In fact, there are some functions which just can't be defined by the first scheme, which can be defined by the second scheme - for instance, let $F(n)$ be the leading digit of $n!$. Since $F$ is neither injective nor eventually periodic, $F$ can't be defined by the first scheme (exercise), but you can define it according to the second.