# Definition:Primitive Recursion/One Variable

Jump to navigation
Jump to search

## Definition

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:

- $\forall n \in \N: h \left({n}\right) = \begin{cases} a & : n = 0 \\ g \left({n-1, h \left({n-1}\right)}\right) & : n > 0 \end{cases}$

## Also see

It can be seen that this is a special case of primitive recursion on several variables, with $k = 0$ and $f$ replaced by the constant function $f_a$.