Representing Recursion and Primitive Recursion diagrammatically

Question

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!

Answer 1

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.

Primitive recursive functions are those that can be computed (from the trivial initial functions) by using for loops as the basic programming structure.

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.

Recursive ($\mu$-recursive) functions are those that can be computed (from the trivial initial functions) by using for loops and/or do until loops.

'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.]