Implicit recursion-theoretic characterizations of counting classes

We give recursion-theoretic characterizations of the counting class #P, the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels {#P-k}(k is an element of N) of the counting hierarchy of functions FCH, which result from allowing queries to functions of the previous level, and FCH itself as a whole. This is done in the style of Bellantoni and Cook's safe recursion, and it places #P in the context of implicit computational complexity. Namely, it relates #P with the implicit characterizations of FPTIME (Bellantoni and Cook, Comput Complex 2:97-110,1992) and FPSPACE (Oitavem, Math Log Q 54(3):317-323, 2008), by exploiting the features of the tree-recursion scheme of FPSPACE.