Fix an endofunctor $𝐹:\mathrm{𝒞︀}\to \mathrm{𝒞︀}$. A coalgebra $𝛾:𝑋\to 𝐹𝑋$ is recursive when for every algebra $𝛼:𝐹𝐵\to 𝐵$ there is exactly one hylomorphism $ℎ:𝑋\to 𝐵$ from $𝛾$ to $𝛼$, that is, exactly one solution of

Equivalently, the functor $\text{𝖧𝗒𝗅𝗈}(𝛾,-)$ of the hylomorphism profunctor is constantly a singleton.

Recursiveness is a coalgebraic form of well-foundedness: $𝛾$ decomposes each input into subproblems, and recursiveness says that every divide-and-conquer program built on this decomposition has a unique meaning, without mentioning an order on inputs. [1] use recursive coalgebras on categories of indexed families to obtain algorithms that are correct by the type of the map they compute.

Example. If $(𝜇𝐹,\text{𝗂𝗇})$ is an initial algebra, then $\text{𝗂𝗇}$ is invertible (Lambek’s lemma) and ${\text{𝗂𝗇}}^{-1}:𝜇𝐹\to 𝐹(𝜇𝐹)$ is a recursive coalgebra. Precomposing with the isomorphism $\text{𝗂𝗇}$, the equation $ℎ={\text{𝗂𝗇}}^{-1}\star 𝐹ℎ\star 𝛼$ is equivalent to $\text{𝗂𝗇}\star ℎ=𝐹ℎ\star 𝛼$, which says $ℎ$ is an algebra map out of the initial algebra; there is exactly one, $\text{𝖿𝗈𝗅𝖽}𝛼$.

The dual notion is a corecursive algebra.