I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how Recursive functions in their various different forms could be represented this way.
If anyone knows of a method of drawing diagrams to visualise the behaviour of recursion and recursive functions, I'd love to learn more about it on this thread!
On
There is a way to visualize in an algebraic manner the recursive operator of the Primitive Recursive Function class: the Natural Numbers Object (NNO) in the context of a cartesian (or even monoidal) category. It allows to define Primitive Recursion by showing the relations diagramatically. You can see an extensive definition and characterizations in ncatlab.org/nlab/show/natural+numbers+object
On the other hand, in this paper you can find a whole description of the class in terms of trees where the vertices are functions labelled by the usual operators.
The latter description makes use of the NNO diagram (and others).
I'm not sure what a diagrammatic representation would come to here. But here's a vivid and memorable way to think about the difference between primitive recursive and recursive functions.
There are bounded loops [we know as we enter how many cycles to execute]. We can, though, nest them one inside the other, and chain together such nested loops. 'For loops' correspond to definitions by primitive recursion.
'Do until' loops involve unbounded searches until some condition is satisfied [as we enter the loop, we don't know how many times we will need to cycle around], so correspond to definitions by minimization.
So perhaps what needs to be 'diagrammed', if anything, is the difference between bounded and unbounded loopings.
[For more about this way of thinking about the difference between primitive recursive and $\mu$-recursive functions, see my Introduction to Gödel's Theorems, the first edition of which should be in most uni libraries.]