primitive recursive function

Primitive recursive functions are a class of functions in logic and mathematics that can be defined by a procedure that repeatedly applies a given relation or routine operation to known values. This method was developed to avoid paradoxes associated with infinite classes by specifying function ranges without referring to infinite sets.1

A simpler form, "primitive recursive," can be calculated using basic arithmetic operations and a recursive definition. For example, addition can be defined recursively: x + 0 = x, and x + Sy = S(x + y), where S represents the successor function.2

More general "recursive functions" have graphs that are recursively enumerable. All recursive functions are calculable, and conversely, only recursive functions can be calculated by a theoretical machine, a concept formalized by the Church-Turing thesis. The theory of recursive functions is fundamental to understanding computability and has origins in logic, particularly in addressing the decision problem.23