My proof of the recursion principle (without the axiom of replacement) (The proof in my book uses the axiom of replacement. My proof doesn't use it. Any hints and recommendations are welcomed.)

The recursion principle
Let $y_0$ be any element of a set $Y$ and $h: \Bbb N \times Y \to Y$ a
  function on pairs $(x,y) \in \Bbb N \times Y$. Then there exists a
  unique function $f:\Bbb N \to Y$ such that
$f(0) = y_0$ and $f(n^+) = h(n, f(n))$
where $n^+ = n \cup \{n\}$

$\Bbb N$ is defined as the "smallest" inductive set and we can show that it has basic properties (like that ∈ linearly orders $\Bbb N$) without using recursion. So we can use these properties during the proof.
Let's create a set of functions $F$ such that a function $f$ is in $F$ if $f$ has a domain $n \in \Bbb N$ and $Y$ as its codomain, also $f(0) = y_0$ and if $m, m^+$ are both in its domain, then $f(m^+) = h(m, f(m))$.
We wish to show that for every $n \in \Bbb N$ and $n \ne \emptyset$ there is a unique function in $F$ with the domain $n$. We define a set $A = \{x \in \Bbb N: x = \emptyset$ or $x$ is a domain for some $f \in F$ and $f$ is the only function with this domain in $F\}$. $0$ (or $\emptyset$) is in $A$ by definition. The function $\{(0, y_0)\}$ is in $F$ and it is the only function with the domain $\{0\}$ that contains the element $(0, y_0)$, so $1 \in A$. If $n \in A$ and $n \ne 0$ then there is $f_n \in F$ defined from all numbers from $0$ to $n^-$. We create a function $f_{n^+}$, that has the same elements as $f_n$ and we define $f_{n^+}(n) = h(n, f_{n}(n^-))$, so this new function has the domain $n^+$. It is clear that $f_{n^+}$ is in $F$. Now we show that it is unique. Suppose it is not, and there is another function $g$ in $F$ with the same domain as $f_{n^+}$. Then $g$ must agree with $f_{n^+}$ on all numbers except $n$, otherwise we would be able to remove the pair $(n, y)$ from $g$ and show that there is a new function $f_n' \in F$ not equal to $f_n$ and they have the same domain, but we have proved that $f_n$ is unique. $f_{n^+}$ and $g$ also agree on $n$, because $f_{n^+}(n) = h(n, f_{n^+}(n^-)) = h(n, g(n^-)) = g(n)$. So $n^+ \in A$ and hence $\Bbb N = A$.
Now we wish to show that for every $f, g \in F$, either $f \subseteq g$ or $g \subseteq f$. 
We define a set $A = \{x \in \Bbb N: x = \emptyset$ or $x$ is a domain of a function $f \in F$ and $f$ has this property that for any $g \in F$ either $f \subseteq g$ or $g \subseteq f\}$. $0$ (or $\emptyset$) is in $A$ by definition. Since $\{(0, y_0)\}$ is a subset of any function in $F$, then $1 \in A$. Suppose $n \in A$ and $n \ne 0$ then it corresponds to the function $f_n$. Also there is a function $f_{n^+}$ in $F$. For any $g \in F$, either $g \subseteq f_n$ or $f_n \subseteq g$. If $g \subseteq f_n$ then $g \subseteq f_n \subseteq f_{n^+}$ (it includes the case when $g = f_n$), otherwise $f_n \subset g$, then $f_{n^+}$ is equal to $g$ for the values below and equal to $n^-$ and also for $n$ because $f_{n^+}(n) = h(n, f_{n^+}(n^-)) = h(n, f_n(n^-)) = h(n, g(n^-)) = g(n)$ So $f_{n^+} \subseteq g$. It shows that $n^+ \in A$ and hence $\Bbb N = A$.
I say that $\phi = \bigcup F$ is the function we are looking for. 1) Domain of every function in $F$ is a subset of $\Bbb N$, then the domain of $\phi$ is a subset of $\Bbb N$. Also for every $n \in \Bbb N$ there is a function in $F$ that has $n$ in its domain, so the domain of $\phi$ is equal to $\Bbb N$. 2) There are no two pairs in $\phi$ with the same first part and different second parts. For if it is the case, then let's say one of the pairs belongs to $f \in F$ and the other belongs to $g \in F$, it would contradict the fact that either $f \subseteq g$ or $g \subseteq f$. 3) It is impossible that $\phi(n^+) \neq h(n, \phi(n))$. For suppose it is the case, then using the fact that for any two functions in $F$, one is a subset of the other, we can show that there must be a function $f \in F$ and for this $n$, $f(n^+) \neq h(n, f(n))$ contradicting the requirement for $f$ to be in $F$. $\square$
 A: Below you'll find another proof,
adapted from Nathan Jacobson, "Basic Algebra I", RECURSION THEOREM in section 0.4.
It never does any harm to know more than one proof.
Your proof builds the required function $f$
by patching it together from a coherent set of partial functions.
The alternative proof constructs (the diagram of) the function $f$
as the smallest subset $U$ of $\mathbb{N}\!\times\!Y$ closed under the closure rules
$(0,y_0)\in U$ (the single nullary rule)
and $(n,y)\in U\Rightarrow (n^+,h(n,y))\in U$ (unary rules);
that is, $f=\mathit{rec}(\varnothing)$,
where $\mathit{rec}=\mathit{rec}_{y_0,h}$ is the closure operator
acting on the subsets of $\mathbb{N}\!\times\!Y$
that is defined by these closure rules.
The 'standard' set $\mathbb{N}$ of natural numbers has
$0=\varnothing$ and $n^+=n\cup\{n\}$.
We do not want to be aware of the peculiarities
of the specific structure $(\mathbb{N},0,(\text{-})^+)$;
the important thing are the structure's properties embodied in the Peano's axioms.
To achieve the desired unawareness,
we consider any structure $(N,o,\sigma)$,
where $N$ is a set, $o\in N$, and $\sigma\colon N\to N : x\mapsto\sigma x$,
and the following conditions are satisfied (Peano's axioms):


*

*$\sigma x\neq o$ for every $x\in N$;

*$\sigma$ is injective;

*Axiom of induction: if $X\subseteq N$, $o\in X$,
and $x\in X\Rightarrow\sigma x\in X$ for every $x\in X$,
then $X=N$.



Primitive recursion theorem
Let $Y$ be a set, $a\in Y$, and $h\colon N\!\times\!Y\to Y$.
  Then there exists a unique function $f\colon N\to Y$
  such that [init] $f(o)=a$, and [step] $f(\sigma x)=h(x,f(x))$ for every $x\in N$.

Proof.
Let $\mathcal{U}$ be the set of all subsets $U$ of $N\!\times\!Y$
that have the following two properties:
(i) $(o,a)\in U$,
(ii) if $(x,y)\in U$ then $(\sigma x,h(x,y))\in U$;
note that $\mathcal{U}$ is not empty because $N\!\times\! Y$ belongs to it.
Let $f$ be the intersection of all sets in $\mathcal{U}$;
clearly $f\in\mathcal{U}$.
We shall prove that $f$ is (the diagram of) a function
that satisfies the conditions [init] and [step],
and that it is the only such function.
Claim: for every $x\in N$ there exists $y\in Y$ so that $(x,y)\in f$.
$\quad$Let $T$ be the set of all $x\in N$ for which $(x,y)\in f$ for some $y\in Y$.
We have $o\in T$ since $(o,a)\in f$.
Let $x\in T$, which means that $(x,y)\in f$ for some $y\in Y$;
but then $(\sigma x,h(x,y))\in f$ with $h(x,y)\in Y$, thus $\sigma x\in T$.
It follows that $T=N$, and the claim is proved.
Claim: if $(\sigma x,z)\in f$,
then there exists $y\in Y$ such that $(x,y)\in f$ and $z=h(x,y)$.
$\quad$Suppose the contrary, that there exists $(\sigma x,z)\in f$
such that $z\neq h(x,y)$ for all $y\in Y$.
Then $f':=f\setminus\{(\sigma x,z)\}\in\mathcal{U}$.
First, $(o,a)\in f'$ because $(o,a)\in f$,
while $\sigma x\neq o$ shows that $(o,a)\neq(\sigma x,z)$.
Next, suppose that $(x',y')\in f'$; then $(\sigma x',h(x',y'))\in f$.
We cannot have $(\sigma x',h(x',y'))=(\sigma x,z)$,
since this implies that $x'=x$ and hence that $z=h(x,y')$,
which contradicts the assumption that $z\neq h(x,y)$ for all $y\in Y$.
We see that indeed $f'\in\mathcal{U}$, which contradicts the fact
that $f$ is the smallest set in $\mathcal{U}$.
This contradiction proves the claim.
Claim: if $(x,y)\in f$ and $(x,z)\in f$, then $y=z$.
$\quad$Let $S$ be the set of all $x\in N$
for which $(x,y)\in f$ and $(x,z)\in f$ implies $y=z$ for all $y,z\in Y$.
First, $o\in S$.
Suppose the contrary;
then $(o,b)\in f$ for some $b\neq a$,
and $f':=f\setminus\{(o,b)\}\in\mathcal{U}$
because $(o,a)\in f'$ and $\sigma x\neq o$ for all $x\in N$;
but we cannot have $f'\in\mathcal{U}$.
Next, suppose that $x\in S$ and that $(\sigma x,y)\in f$ and $(\sigma x,z)\in f$.
There exist $y',z'\in Y$
such that $(x,y')\in f$ and $y=h(x,y')$ and $(x,z')\in f$ and $z=h(x,z')$;
then $x\in S$ implies $y'=z'$, which implies $y=z$.
It follows that $\sigma x\in S$.
We conclude that $S=N$, and the claim is proved.
We have proved that $f$ is a function $N\to Y$.
Since the function $f$ belongs to $\mathcal{U}$,
it satisfies the conditions [init] and [step].
Uniqueness of $f$.
$\quad$Suppose that a function $g\colon N\to Y$
satisfies the conditions [init] and [step].
Then $g\in\mathcal{U}$ and hence $g\supseteq f$,
which implies $g=f$ because $f$ and $g$ are functions. Done.
You can use the Primitive recursion theorem to prove the following.
If $(N',o',\sigma')$ is another structure satisfying the Peano's axioms,
then there exists a unique function $f\colon N\to N'$
such that $f(o)=o'$ and $f(\sigma x)=\sigma' f(x)$ for all $x\in N$;
moreover, $f$ is a bijection, and its inverse satisfies the conditions
$f^{-1}(o')=o$ and $f^{-1}(\sigma x')=\sigma f^{-1}(x')$ for all $x'\in N'$.
(Hint: apply the Primitive recursion theorem
in the direction $N\to N'$ with $h(x,x')=\sigma' x'$,
and also in the opposite direction $N'\to N$ with $h'(x',x)=\sigma x$.)
A: In the previous answer
I presented an alternative proof of the recursion principle,
adapted from the proof of RECURSION THEOREM
in section 0.4 of Nathan Jacobson's "Basic Algebra I".
Alas, I followed the proof in the book to closely,
and so the adapted proof inherited several unwieldy reasonings by contradiction.
Since then I have straightened the proof,
eliminating all appearances of reductio ad impossibilem,
and decided to submit the modified proof in a separate answer.
Yes, I agree, I could just edit the proof in the previous answer.
But, I believe that "Mathematics Stack Exchange"
is not just about mathematical results (with proofs),
but also about the know-how of doing mathematics.
In this case we take a proof containing some convoluted arguments,
and by tweaking it here and there convert it into a better, cleaner proof;
with both proofs side by side one can clearly see how this is done.
Certain parts of the modified proof, and of the introduction leading to it,
are identical to those in the previous answer,
so there is some repetition,
which, however, makes the present exposition self-contained.
As in the previous answer,
the proof is not restricted to the particular structure $(\mathbb{N},0,(\text{-})^+)$.
Instead we consider any "natural numbers structure" $(N,o,\sigma)$,
where $N$ is a set, $o\in N$, $\sigma\colon N\to N : x\mapsto\sigma x$,
and the following conditions (Peano's axioms) are satisfied:


*

*$\sigma x\neq o$ for every $x\in N$;

*$\sigma$ is injective;

*Induction: if $X\subseteq N$, $o\in X$,
and $x\in X$ implies $\sigma x\in X$ for every $x\in X$,
then $X=N$.
$~$



Primitive recursion theorem
Let $Y$ be a set, $a\in Y$, and $h\colon N\!\times\!Y\to Y$.
  Then there exists a unique function $f\colon N\to Y$
  such that [init] $f(o)=a$, and [step] $f(\sigma x)=h(x,f(x))$ for every $x\in N$.

Proof.
Let $\mathcal{U}$ be the set of all subsets $U$ of $N\!\times\!Y$
that have the following two properties:
(i) $(o,a)\in U$,
(ii) if $(x,y)\in U$ then $(\sigma x,h(x,y))\in U$;
note that $\mathcal{U}$ is not empty because $N\!\times\! Y$ belongs to it.
Let $f$ be the intersection of all sets in $\mathcal{U}$;
clearly $f\in\mathcal{U}$.
We shall prove that $f$ is (the diagram of) a function
that satisfies the conditions [init] and [step],
and that it is the only such function.
For every $x\in N$ there exists $y\in Y$ so that $(x,y)\in f$.
$\quad$Let $T$ be the set of all $x\in N$ for which $(x,y)\in f$ for some $y\in Y$.
We have $o\in T$ since $(o,a)\in f$.
Let $x\in T$, which means that $(x,y)\in f$ for some $y\in Y$;
but then $(\sigma x,h(x,y))\in f$ with $h(x,y)\in Y$, thus $\sigma x\in T$.
It follows that $T=N$.
Every pair in $f$ is either $(o,a)$,
or it is of the form $(\sigma x,h(x,y))$ for some $(x,y)\in f$,
but not both (that is, the disjunction is exclusive).
$\quad$Let $f'$ be the set consisting of
the pair $(o,a)$ and of all pairs $(\sigma x,h(x,y))$ for $(x,y)\in f$.
Clearly $f'\subseteq f$.
On the other hand $f'\in\mathcal{U}$:
$(o,a)\in f'$,
and if $(x,y)\in f'\subseteq f$, then $(\sigma x,h(x,y))\in f$,
thus $(\sigma x,h(x,y))\in f'$ by the definition of $f'$.
So we have $f'\supseteq f$, and hence $f'=f$.
In conclusion note that a pair $(\sigma x,z)\in f$
is always different from $(o,a)$ because $\sigma x\neq o$.
$\quad$(This result enables us to get rid of reasonings by contradiction
in the previous proof.)
If $(\sigma x,z)\in f$ for some $x\in N$,
then there exists $y\in Y$ such that $(x,y)\in f$ and $z=h(x,y)$.
$\quad$Let $(\sigma x,z)\in f$.
Then $(\sigma x,z)=(\sigma x',h(x',y))$ for some $(x',y)\in f$.
But $\sigma x'=\sigma x$ implies $x=x'$, thus $z=h(x,y)$.
If $(x,y)\in f$ and $(x,z)\in f$, then $y=z$.
$\quad$Let $S$ be the set of all $x\in N$
for which $(x,y)\in f$ and $(x,z)\in f$ implies $y=z$ for all $y,z\in Y$.
First, $o\in S$,
because $(o,a)$ is the only pair in $f$ with the first component $o$.
Next, suppose that $x\in S$, and that $(\sigma x,y)\in f$ and $(\sigma x,z)\in f$.
There exist $y',z'\in Y$
such that $(x,y')\in f$ and $y=h(x,y')$ and $(x,z')\in f$ and $z=h(x,z')$;
then $x\in S$ implies $y'=z'$, which implies $y=z$.
It follows that $\sigma x\in S$.
We conclude that $S=N$.
We have proved that $f$ is a function $N\to Y$.
Since the function $f$ belongs to $\mathcal{U}$,
it satisfies the conditions [init] and [step].
Uniqueness of $f$.
$\quad$Suppose that a function $g\colon N\to Y$
satisfies the conditions [init] and [step].
Then $g\in\mathcal{U}$ and hence $g\supseteq f$,
which implies $g=f$ because $f$ and $g$ are functions. Done.
A: You'll hardly believe it, but I managed to come up with
yet another proof of the recursion principle.
(If you think that this is too much of a good thing,
just say it and I will delete the present answer.)
The new proof is a close cousin of your proof,
since it builds the function determined by the recurrence rules
from partial functions;
it departs from your proof in that it obtains the desired total function
by reading off the 'diagonal' values of partial functions,
instead of taking the union of the partial functions
(that is, the union of their diagrams).
As before, we avoid working only
with the particular 'standard' structure $(\mathbb{N},0,(\text{-})^+)$,
but consider instead any "natural numbers structure" $(N,o,\sigma)$,
where $N$ is a set, $o\in N$, $\sigma\colon N\to N : x\mapsto\sigma x$,
and the Peano's axioms are satisfied:


*

*$\sigma x\neq o$ for every $x\in N$;

*$\sigma$ is injective;

*Induction: if $X\subseteq N$, $o\in X$,
and $x\in X$ implies $\sigma x\in X$ for every $x\in X$,
then $X=N$.


The induction axiom is usually applied as reasoning by induction:
let $P(x)$ be a property of $x\in N$;
if $P(o)$, and $P(x)$ imples $P(\sigma x)$ for every $x\in N$,
then $P(x)$ for every $x\in N$.
Before we confront the recursion principle,
we are going to gather some simple facts about the structure $(N,o,\sigma)$.
For the standard structure $(\mathbb{N},0,(\text{-})^+)$
you are given these facts (almost) gratis,
so you will probably consider deducing them from Peano's axioms a waste of time.
However, we want the generality offered by arbitrary "natural numbers structures".
A~standard natural number $n\in\mathbb{N}$ is a~set
whose composition is not so simple as one would think at first sight.
Have you ever written out in full at least a few small standard natural numbers?
If we write the empty set as $\{\}$,
then the written expression for the set $n$ consists of $2^n$ pairs of braces
and, when $n\geq 2$, also of $2^{n-1}-1$ commas;
for example,
$$4 = \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\}~.$$
If we write the empty set as $\varnothing$,
then the expression for $n\geq 1$ consists of $2^{n-1}$ pairs of braces
and of $2^{n-1}$ occurences of $\varnothing$.
When you are working with the standard set $\mathbb{N}$
you are always in danger
that your reasoning will get entangled with the peculiar construction
of standard natural numbers.
It is better, and safer, to regard $\mathbb{N}$
as just one of possible realizations (or implementations) of the idea of natural numbers,
and rely only on the essential properties of natural numbers
expressed by Peano's axioms.
Besides that, it is always fascinating watching Peano's axioms in action.
We are going to reason in small steps,
with each step establishing one little property.
Let $x\in N$.
Let $\mathcal{S}_x$ be the set of all subsets $X$ of $N$
satisfying the conditions
[$x{\in}$] $x\in X$, and
[$\leftarrow$] for every $y\in N$, if $\sigma y\in X$ then $y\in X$.
Always $N\in\mathcal{S}_x$.
We set $S_x:=\bigcap\mathcal{S}_x$.
Clearly $S_x\in\mathcal{S}_x$, that is, $S_x$ satisfies [$x{\in}$] and $[\leftarrow]$.
$S_o=\{o\}$.
$\quad$If $X\subseteq N$ satisfies [$o{\in}$] and [$\leftarrow$], then $\{o\}\subseteq X$.
Since $\{o\}$ already satisfies the conditions [$o{\in}$]
and [$\leftarrow$]
(this one vacuously, since there is no $y\in\mathbb{N}$ such that $\sigma y\in\{o\}$),
it follows that $S_o=\{o\}$.
$S_x\subseteq S_{\sigma x}$ for every $x\in N$.
$\quad$If $X\subseteq N$ satisfies [$\sigma x{\in}$] and [$\leftarrow$],
then $\sigma x\in X$ by [$\sigma x{\in}$] and hence $x\in X$ by [$\leftarrow$],
thus $X$ satisfies [$x{\in}$] and [$\leftarrow$], whence $S_x\subseteq X$;
in particular $S_x\subseteq S_{\sigma x}$.
$o\in S_x$ for every $x\in N$.
$\quad$Proof is by induction on $x$.
We have $o\in\{o\}=S_o$.
If $o\in S_x$ for an $x\in N$, then $o\in S_{\sigma x}$
because $S_x\subseteq S_{\sigma x}$.
$S_{\sigma x}=S_x\cup\{\sigma x\}$ for all $x\in N$.
$\quad$Let $x\in N$.
The set $S':=S_x\cup\{\sigma x\}$ is a subset of $S_{\sigma x}$
because $S_x\subseteq S_{\sigma x}$ and $\sigma x\in S_{\sigma x}$.
The set $S'$ satisfies [$\sigma x{\in}$] by construction.
If $y\in N$ and $\sigma y\in S'$, then $\sigma y\in S_x$ or $\sigma y=\sigma x$;
if $\sigma y\in S_x$ then $y\in S_x\subseteq S'$;
if $\sigma y=\sigma x$, then $y=x\in S_x\subseteq S'$
because $\sigma$ is injective.
So $S'$ satisfies [$\leftarrow$], therefore $S'=S_{\sigma x}$.
$\sigma x\notin S_x$ for every $x\in N$.
$\quad$Proof is by induction on $x$.
First, $\sigma o\notin\{o\}=S_o$.
Next, let $x\in N$.
We have to prove that $\sigma x\notin S_x$ implies $\sigma\sigma x\notin S_{\sigma x}$;
we shall prove the equivalent contrapositive implication
$\sigma\sigma x\in S_{\sigma x} \Rightarrow \sigma x\in S_x$.
So suppose that $\sigma\sigma x\in S_{\sigma x}=S_x\cup\{\sigma x\}$.
If $\sigma\sigma x\in S_x$, then $\sigma x\in S_x$.
If $\sigma\sigma x=\sigma x$, then $\sigma x=x\in S_x$
because $\sigma$ is injective.
Let us sum up the gathered properties of the sets $S_x$:
$x\in S_x$ and $\sigma y\in S_x\Rightarrow y\in S_x$ (by definition);
$S_o=\{o\}$; $o\in S_x$;
$S_{\sigma x}=S_x\cup\{\sigma x\}$, where $\sigma x\notin S_x$.
We shall (mostly) use these properties without explicitly referring to them.
We are ready to tackle the recursion principle.
$~$

Primitive recursion theorem
Let $Y$ be a set, $a\in Y$, and $h\colon N\!\times\!Y\to Y$.
  Then there exists a unique function $f\colon N\to Y$
  such that [init] $f(o)=a$, and [step] $f(\sigma x)=h(x,f(x))$ for every $x\in N$.  

Proof.
First we prove the existence and uniqueness
of partial functions satisfying the (restricted) recurrence conditions.
For every $x\in N$
there exists a unique function $f_x\colon S_x\to Y$
that satisfies the conditions
[init] $f_x(o)=a$, and
[step$|S_x$]
for every $y\in N$ such that $\sigma y\in S_x$ (and hence $y\in S_x$),
$f_x(\sigma y) = h(y,f_x(y))$.
Moreover, $f_{\sigma x}(\sigma x)=h(x,f_x(x))$ for every $x\in N$.
$\quad$Proof is by induction on $x$.
The assertion is true for $x=o$,
because the only function $S_o\to Y$ satisfying [init] is $f_o\colon o\mapsto a$,
and this function also satisfies (vacuously) [step$|S_o$].
$\quad$Now assume that the assertion is true for $x\in\mathbb{N}$.
Suppose that $g\colon S_{\sigma x}\to Y$ satisfies [init] and
[step$|S_{\sigma x}$].
Then the restriction of $g$ to $g'\colon S_x\to Y$ satisfies [init] and [step$|S_x$],
thus $g'=f_x$ by induction hypothesis.
Since $\sigma x\in S_{\sigma x}$ and $g$ satisfies [step$|S_{\sigma x}$],
we must have $g(\sigma x)=h(x,g(x))=h(x,g'(x))=h(x,f_x(x))$.
This proves that $g$ is unique, provided that it exists.
Now we define the function $g\colon S_{\sigma x}\to Y$
so that $g(y)=f_x(y)$ for $y\in S_x$
and that $g(\sigma x)=h(x,f_x(x))$ at $\sigma x\notin S_x$.
Since $g(o)=f_x(o)=a$, $g$ satisfies [init].
Suppose that $y\in N$ and $\sigma y\in S_{\sigma x}$.
If $\sigma y\in S_x$, then $y\in S_x$
and $g(\sigma y)=f_x(\sigma y)=h(y,f_x(y))=h(y,g(y))$.
If $\sigma y=\sigma x$, then $y=x\in S_x$
and $g(\sigma x)=h(x,f_x(x))=h(x,g(x))$.
Thus $g$ satisfies [step$|S_{\sigma x}$].
We have proved the existence and uniqueness of the function $f_{\sigma x}=g$.
The function $f\colon N\to Y$ defined by $f(x):= f_x(x)$ satisfies [init] and [step].
Uniqueness.
Suppose $g\colon N\to Y$ satisfies [init] and [step].
For every $x\in N$ the restriction of $g$ to $g_x\colon S_x\to Y$
satisfies [init] and [step$|S_x$],
thus $g_x=f_x$ and $g(x)=g_x(x)=f_x(x)=f(x)$. Done
$~$
For the standard natural numbers we have $S_x=x^+=x\cup\{x\}$ for $x\in\mathbb{N}$.
In this special case the properties of the sets $S_x$,
listed just before the Primitive recursion theorem,
are easy to prove and you have them at hand almost for free.
Then do this: specialize $(N,o,\sigma)$ to $(\mathbb{N},0,(\text{-})^+)$;
this will convert the Primitive recursion theorem and its proof
into your Recursion principle theorem and its proof.
This new proof of the Recursion principle theorem
follows the same leading idea as your proof
(it builds the total function from partial functions),
but it is shorter and more intuitive.
After this surfeit of serious elementary set theory,
let me conclude, on a lighter note, with a nice combinatorial problem.
We can write the set $2\in\mathbb{N}$ in precisely two ways
(barring repeated elements):
$2 = \{\varnothing,\{\varnothing\}\} = \{\{\varnothing\},\varnothing\}$.
There are already $12$ ways to write the set $3\in\mathbb{N}$.
In general, given any $n\in\mathbb{N}$,
let $G(n)$ be the number of different ways to write the set $n$,
where whenever you write a set by listing its elements,
you take care that the listed elements are different sets
(that is, no set is listed twice).
Then $G(0)=1$, and $G(n)=\prod_{k=1}^n k^{2^{n-k}}$ for $n\geq 1$.
Prove it, it's fun.
Now consider the set $10\in\mathbb{N}$.
In order to write down this set
you need $512$ pairs of braces, then $512$ $\varnothing$'s, and also $511$ commas,
all in all $2047$ symbols;
this can be done, it will fit in a single printed page, with space to spare.
However, do not ever try to write out the set $10$ in all possible ways,
not even with the help of a computer.
Why?  Because $G(10)\doteq 5.836\cdot\!10^{224}$.
