primitive recursion

English

Noun

primitive recursion (countable and uncountable, plural primitive recursions)

1. (computing theory) Recursion to a fixed depth.
2. (computing theory) The operator $\rho$ that creates a new function from two functions $g$ and $h$ such that:
   $\begin{array}{cc}\rho (g,h)(0,x_1,\dots ,x_k)& =g(x_1,\dots ,x_k)\\ \rho (g,h)(y+1,x_1,\dots ,x_k)& =h(y,\rho (g,h)(y,x_1,\dots ,x_k),x_1,\dots ,x_k)\end{array}$.

See also

• primitive recursive
• recursion
• primitive recursion on Wikipedia.Wikipedia