# Primitive recursion

A means of defining functions with natural number arguments and values. One says that an $(n+1)$-place function $f(x_1,\dots,x_n,y)$ is obtained by primitive recursion from an $n$-place function $g(x_1,\dots,x_n)$ and an $(n+2)$-place function $h(x_1,\dots,x_n,y,z)$ if for all natural number values of $x_1,\dots,x_n,y$ one has

$$f(x_1,\dots,x_n,0)=g(x_1,\dots,x_n)$$

and

$$f(x_1,\dots,x_n,y+1)=h(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y)).$$

For given $g$ and $h$ such a function $f$ exists always and is unique. For $n=0$ the defining equations for $f$ can be written as

$$f(0)=a,\quad f(x+1)=h(x,f(x)).$$

A fundamental property of primitive recursion is that for any meaningful specification of the notion of computability, a function $f$ obtained from computable functions $g$ and $h$ by means of primitive recursion is itself computable (cf. Computable function). Primitive recursion is one of the basic ways for generating all primitive recursive and all partial recursive functions from an initial set of basic functions (cf. Primitive recursive function; Partial recursive function).

How to Cite This Entry:
Primitive recursion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Primitive_recursion&oldid=34257
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article