Definition:Primitive Recursion
Definition
Primitive Recursion on Several Variables
Let $f: \N^k \to \N$ and $g: \N^{k + 2} \to \N$ be functions.
Let $\tuple {n_1, n_2, \ldots, n_k} \in \N^k$.
Then the function $h: \N^{k + 1} \to \N$ is obtained from $f$ and $g$ by primitive recursion if and only if:
- $\forall n \in \N: \map h {n_1, n_2, \ldots, n_k, n} = \begin {cases}
\map f {n_1, n_2, \ldots, n_k} & : n = 0 \\ \map g {n_1, n_2, \ldots, n_k, n - 1, \map h {n_1, n_2, \ldots, n_k, n - 1} } & : n > 0 \end {cases}$
Primitive Recursion on One Variable
Let $a \in \N$ be a natural number.
Let $g: \N^2 \to \N$ be a function.
Then the function $h: \N \to \N$ is obtained from the constant $a$ and $g$ by primitive recursion if and only if:
- $\forall n \in \N: \map h n = \begin {cases}
a & : n = 0 \\ \map g {n - 1, \map h {n - 1} } & : n > 0 \end{cases}$
Primitive Recursion on Partial Functions
Let $f: \N^k \to \N$ and $g: \N^{k+2} \to \N$ be partial functions.
Let $\tuple {n_1, n_2, \ldots, n_k} \in \N^k$.
Then the partial function $h: \N^{k + 1} \to \N$ is obtained from $f$ and $g$ by primitive recursion if and only if:
- $\forall n \in \N: \map h {n_1, n_2, \ldots, n_k, n} \approx \begin {cases}
\map f {n_1, n_2, \ldots, n_k} & : n = 0 \\ \map g {n_1, n_2, \ldots, n_k, n - 1, \map h {n_1, n_2, \ldots, n_k, n - 1} } & : n > 0 \end{cases}$
where $\approx$ is as defined in Partial Function Equality.
Note that $\map h {n_1, n_2, \ldots, n_k, n}$ is defined only when:
- $\map h {n_1, n_2, \ldots, n_k, n - 1}$ is defined
- $\map g {n_1, n_2, \ldots, n_k, n - 1, \map h {n_1, n_2, \ldots, n_k, n - 1} }$ is defined.