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))$.