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{aligned}\rho (g,h)(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\\rho (g,h)(y+1,x_{1},\ldots ,x_{k})&=h(y,\rho (g,h)(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,\end{aligned}}$.

See also

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