Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
I am not sure I totally understand your question. For example, people have used all sorts of methods including UML. Is something like this Recursion Diagrams: ideas for a Geometry of Formal Methods the sort of thing you had in mind? Regards – Amzoti Jan 12 '13 at 19:07
Thanks for your comment- it might well be the sort of thing I had in mind! Looks really interesting anyway. I have edited the second paragraph in my question, so that it is hopefully a little clearer what I mean. In general, I'm interested in any form of visual representation of recursion, and recursive functions. – Seraphina Jan 12 '13 at 19:21
up vote 1 down vote accepted

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

share|cite|improve this answer
Thanks for your excellent description of the difference between how primitive recursive and recursive functions behave. I can now see that the difference lies in the nature of the loops. Depicting this will be an interesting project- I'll have to post it on here, as and when I come up with something! Your book looks really interesting- I shall have to track it down. – Seraphina Jan 19 '13 at 17:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.