The proof of recursion with which I’m familiar does not use transitive closure. A version of it can be found on-line in Don Monk’s Advanced Set Theory notes, specifically, as Theorem 4.12 in Chapter 4:
Suppose that $\mathbf G$ is a class function with domain the class of all (ordinary) functions. Then there is a unique class function $\mathbf F$ with domain $\mathrm{On}$ such that for every ordinal $\alpha$ we have $\mathbf F(\alpha)=\mathbf G(\mathbf F\upharpoonright\alpha)$.
This starts on page 19. Roughly speaking the proof is by showing that for each ordinal $\alpha$ there is an approximation $f_\alpha$ to $\mathbf F$ with domain $\alpha$, that these approximations are unique, and that they ‘fit together’ properly, so that one may define $\mathbf F(\alpha)$ as $f_{\alpha+1}(\alpha)$.
Okay ! After some time and a lot of efforts, I managed to find an answer that I find satisfying.
The big problem I had was that I had no way yet to rigorously write a formula that said "$n$ is a successor of $m$" for any natural numbers $n$ and $m$.
I tried to recursively define what it meant to be the "$n$-th successor of $0$" (where we define $0$ to be $\emptyset$), and I was on the right track, but I ran into trouble because I hadn't proven beforehand that I was allowed to define things recursively.
To prove that, there are a quite a few steps I had to take so, for the sake of brevity, I will only provide an outline of the proofs ; if anyone sees this with the same question I had and wants the details, just ask.
The Theorem of Induction states that
$$
\forall A\ (0\in A\ \wedge\ \forall k\in\Bbb N\ (k\in A\Rightarrow\mathcal S(k)\in A))\Rightarrow\Bbb N\subseteq A
$$
It can be proven by showing that $A\cap\Bbb N$ is inductive so
$\Bbb N\subseteq A\cap\Bbb N$ and, since $A\cap\Bbb N\subseteq A$, we conclude that
$\Bbb N\subseteq A$.
To make my life simpler, I then proved that, given a property $P$
$$
[P(0)\,\wedge\,(\,\forall x\ P(x)\Rightarrow P(\mathcal S(n))\,)]\Rightarrow\forall n\in\Bbb N\quad P(n)
$$
It follows directly from 1. Just let $A=\{n\in\Bbb N\mid P(n)\}$ and apply 1. to it.
From there we prove this bad boy, the Recursion Theorem, which says that
$$
\forall X\quad X\neq\emptyset\Rightarrow[\ \forall a\in X\ \forall f:X\rightarrow X\ \exists!F:\Bbb N\rightarrow X\quad \underbrace {F(0)=a\ \wedge\ \forall n\in\Bbb N\enspace F(\mathcal S(n))=f(F(n))}_{\text {(a)}}\ ]
$$
i.e. For all non-empty $X$, $a\in X$ and $f:X\rightarrow X$, there is a unique function $F:\Bbb N\rightarrow X$ such that $\text {(a)}$.
The proof is a long and tedious one which relies on proving that a specific subset of $\Bbb N$ is inductive and, therefore, equal to $\Bbb N$. It gets messy real quick and I got lost multiple time doing it, so I'll redirect you to this book (Naive Set theory, by Paul R. Halmos) on pages 48-49, which is where I got it from.
Finally, armed with 3. we can safely define things recursively.
We apply the recursion theorem with $X=\Bbb N$, an $a\in X$ whose value we don't specify, and $f=\mathcal S$ the successor function. There exists a unique function that satisfies $\text {(a)}$ and, since it depends on $a$ what that function is, lets call it $F_a$. (It also depends on $X$ and $f$, but we fixed their values. Only $a$ is unspecified.) $F_a$ is defined on all of $\Bbb N$.
Let's rewrite the property $\text {(a)}$:
$$
F_a(0)=a\ \wedge\ \forall n\in\Bbb N\enspace F_a(\mathcal S(n))=\mathcal S(F_a(n))
$$
I hope that you'll agree that, for any $n\in\Bbb N$, $F_a(n)$ is the result of applying $\mathcal S$ to $a$ $n$ times over, i.e. the "$n$-th successor of $a$".
Let's now, at last, prove by induction that
$$
\forall n\in\Bbb N\quad F_0(n)=n
$$
i.e. Any natural number $n$ is, in fact, the $n$-th successor of $0$.
Base case: $F_0(0)=0$
Induction step: For a given $n\in\Bbb N$, suppose that $F_0(n)=n$.
$$
F_0(\mathcal S(n))=\mathcal S(F_0(n))\\
\phantom {F_0(\mathcal S(n))}=\mathcal S(n)\phantom {F_0()}
$$
We then conclude that $\Bbb N=\{F_0(n)\mid n\in\Bbb N\}$, i.e. that $\Bbb N$ is the set of $0$ and its successors. And finally, it is done. Sure hope I didn't mess up !
Afterthought: This whole demonstration makes copious use of $\Bbb N$'s definition, it's properties, and results that are deduced from its existence. Therefore, for it to hold, one must first define $\Bbb N$ as the smalest inductive set, and then show that it's the set of $0$ and its successors.
I don't see any way that one could go the other way around, as in how $\Bbb N$ could be defined, from the get-go, to be the set of $0$ and its successors.
Best Answer
You're describing the concept of extension by definitions. If your underlying theory (say ZFC) is strong enough to prove that your proposed function is in fact well defined (in other words, if it can prove $\forall x_1 \ldots x_n \exists ! y \phi (y, x_1 \ldots x_n)$, where $\phi$ is the formula defining your proposed function), then you can extend the language by an additional function symbol $f$ defined by $\phi$.
This extension will always be conservative. Any statement that's true in the base language remains true in the extended language and you can always find a statement in the base language that is provably equivalent to a statement in the extended language.