Primitive recursive function

A function on natural numbers built from zero, successor, and projection functions using composition and primitive recursion. Every such function is total, though some total computable functions are not primitive recursive.

Zero function: A function that returns zero for every input. It is one of the initial functions from which primitive recursive functions are built.
Primitive recursion schema: A formal rule defining a function from a base case and a step that uses its previous value. It expresses the exact recurrence permitted in primitive recursive definitions.
General recursive function: A function computable by unrestricted recursion, including partial functions that may be undefined on some inputs. General recursion allows more than the bounded recursion underlying this class.
Exponentiation: The operation of raising a number to a nonnegative integer power. Repeated multiplication defines exponentiation by primitive recursion.
Successor function: The function that maps each natural number to the next natural number. It supplies the basic step used to generate values and define recursion.
Bounded iteration: Repeated application of an operation a number of times specified by a finite bound. Primitive recursion can implement loops whose iteration count is determined by an input.
Partial recursive function: A function computed by a recursive procedure that may fail to halt on some inputs. Primitive recursive functions are total, unlike the broader partial recursive class.
Euclidean algorithm: An algorithm for finding the greatest common divisor by repeated division with remainder. Its bounded arithmetic operations and recursion can be represented primitively recursively.
Projection function: A function of several arguments that returns one selected argument. Projections provide the input variables needed to combine functions.
Structural recursion: A recursive definition that reduces an input through its finite structure until reaching base cases. On natural numbers, recursion over predecessors gives a concrete structural interpretation.

Linked from 7 pages