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 ${\displaystyle \rho \,}$ that creates a new function from two functions ${\displaystyle g\,}$ and ${\displaystyle h\,}$ such that:
   ${\displaystyle {\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