Primitive recursion — bounded loops, always halt

Parent: recursive-functions

The primitive recursive functions

The smallest class containing the basic functions —

zero Z() = 0, successor S(n) = n+1, projections Pᵢ(x₁,…,xₖ) = xᵢ — and closed under:

composition (plug functions into functions);

primitive recursion: define f by f(0, x) = g(x) and f(n+1, x) = h(n, f(n, x), x), i.e. recurse on a counter n that strictly decreases to a base case.

Everything primitive recursive is total

Every primitive recursive function halts on all inputs — the recursion is driven by a counter that counts down to 0, so it can't run forever. Primitive recursion = bounded for-loops.

What it covers, and its ceiling

Addition, multiplication, exponentiation, factorial, bounded search, primality, gcd, coding/decoding of tuples — essentially every "everyday" total function is primitive recursive.

But the recursion depth is always bounded by the input: no for-loop nesting can encode a search whose length isn't known in advance. So the class is not all of the computable functions — the witness is Ackermann's function, which is total and computable but grows faster than any primitive recursive function. To go further you need unbounded search → general-recursion.