Primitive recursive function

Summary

A primitive recursive function is a function on the natural numbers built from zero, successor and projections by composition and primitive recursion. Primitive recursion defines $f(n + 1)$ from $f(n)$, like a for-loop whose number of steps is fixed in advance. Every primitive recursive function is total and computable, and most functions met in ordinary number theory are primitive recursive. Not every total computable function is primitive recursive; the Ackermann function is the classical example.