Suppose $f: N \rightarrow R $, $g$ is a function of two variables $n
\in N$ and $x \in R$, and $a$ is a real number, $a \in R$.
Definition: $f$ is a (first order) recursive
function if $f(0) = a$ and for all $n$, $f(n+1) = g(n,
f(n))$.
(First Order) Recursive Function Theorem: Given $a \in R$ and
$g$ a function of two variables $n \in N$ and $x \in R$, there is a
unique recursive function $f_{a,g}: N \rightarrow R $ with
$f_{a,g}(0) = a$ and for all $n$, $f_{a,g}(n+1) = g(n, f_{a,g}(n))$.
Suppose $f: N \rightarrow R $, $g$ is a
function of three variables $n \in N$, $x$ and $y \in R$, and $a$ is
a real number, $a \in R$.
Definition: $f$ is a (second order) recursive
function if $f(0) = a$ and for all $n$, $f(n+2) = g(n,
f(n), f(n+1))$.
(Second Order) Recursive Function Theorem: Given $a \in R$
and $g$ is a function of three variables $n \in N$, $x$ and $y \in
R$, there is a unique recursive function $f_{a,g}: N \rightarrow R $
with $f_{a,g}(0) = a$ and for all $n$, $f_{a,g}(n+1) = g(n,
f_{a,g}(n), f_{a,g}(n+1))$.