= Primitive recursive function
{wiki}
= Primitive recursive
{synonym}
In intuitive terms it consists of all integer functions, possibly with multiple input arguments, that can be written only with a sequence of:
* variable assignments
* addition and subtraction
* integer comparisons and if/else
* <for loops>
``
for (i = 0; i < n; i++)
``
and such that `n` does not change inside the loop body, i.e. no <while loops> with arbitrary conditions.
`n` does not have to be a constant, it may come from previous calculations. But it must not change inside the loop body.
<Primitive recursive functions> basically include every integer function that comes up in practice. Primitive recursive functions can have huge complexity, and it strictly contains <EXPTIME>. As such, they mostly only come up in <foundation of mathematics> contexts.
The cool thing about <primitive recursive functions> is that the number of iterations is always bound, so we are certain that they terminate and are therefore <computable>.
This also means that there are necessarily functions which are not <primitive recursive>, as we know that there must exist <uncomputable> functions, e.g. the <busy beaver function>.
Adding unbounded <while loops> of course enables us to simulate arbitrary <Turing machines>, and therefore increases the <complexity class>.
More finely, there are <non-primitive total recursive functions>, e.g. most famously the <Ackermann function>.
Back to article page