The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration.

Iterative characterizations of computable unary functions are useful patterns for the definition of programming languages based on iterative constructs. The features of such a characterization depend on the pairing producing it: this paper offers an infinite class of pairings involving very nice features.

The set, the closure of F, is the closure with respect to substitution and concatenation recursion on notation of a set of basic functions comprehending the set F. By improving earlier work, we show that is the substitution closure of a simple function set and characterize well‐known function complexity classes as the substitution closure of finite sets of simple functions.

A basis for a set C of functions on natural numbers is a set F of functions such that C is the closure with respect to substitution of the projection functions and the functions in F. This paper introduces three new bases, comprehending only common functions, for the Grzegorczyk classes ℰ_n with n ≥ 3. Such results are then applied in order to show that ℰ_{n+1} = K_n for n ≥ 2, where {K_n}n∈ℕ is the Axt hierarchy.