The simplest example [0] (other than Ackerman function et al (i.e. structural recursion) which come up less in practice) is coinduction which can be used to construct infinitely large objects on which you can apply operations that will prove to halt. For example given an infinitely large stream of integers 0, 2, 4, 6, 8, ..., 2*i (i in N) it's trivial to write a halting algorithm that'll sum first N elements of the stream. In short, we need to a way to express that the computation will be bounded by N.

Agda programming language (which requires halting, and therefore is not Turing-Complete) has a robust coinduction support. E.g. in this [1] tutorial you can see it being used to construct decidable languages. A more traditional tutorial to coinduction could be found here [2].

[0] if we count primitive corecursion as "non-primitive recursive" here

[1] https://agda.readthedocs.io/en/v2.6.4.1/language/sized-types...

[2] https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction...