Human cognitive capacity includes recursively definable concepts, which are prevalent in domains involving lists, numbers, and languages. Cognitive science currently lacks a satisfactory explanation for the systematic nature of recursive cognitive capacities. The category-theoretic constructs of initial F-algebra, catamorphism, and their duals, final coalgebra and anamorphism provide a formal, systematic treatment of recursion in computer science. Here, we use this formalism to explain the systematicity of recursive cognitive capacities without ad hoc assumptions (i.e., why the capacity for some recursive cognitive abilities implies the capacity for certain others, to the same explanatory standard used in our account of systematicity for non-recursive capacities). The presence/absence of an initial algebra/final coalgebra implies the presence/absence of all systematically related recursive capacities in that domain. This formulation also clarifies the theoretical relationship between recursive cognitive capacities. In particular, the link between number and language does not depend on recursion, as such, but on the underlying functor on which the group of recursive capacities is based. Thus, many species (and infants) can employ recursive processes without having a full-blown capacity for number and language.