Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 wondered if anyone could recommend any good introductory books on primitive recursive functions. I'm currently working through a Number Theory and Mathematical Logic module, and I'm finding it helpful to look at different books to gain a broader understanding and intuition of topics.

Free e-books/notes would be particularly good to get hold of, or books which are available second-hand at an affordable price.

Thanks in advance!


share|cite|improve this question
It covers much more than just p.r. functions, but Boolos & Jeffrey, Computability and Logic might be worth a look; the Kindle version is under $15. – Brian M. Scott Dec 30 '12 at 14:03
Handouts 10, 11, and 12 for CM10020 from this page might also be helpful. – Brian M. Scott Dec 30 '12 at 14:11
Excellent- thanks! – Seraphina Dec 30 '12 at 15:41
You’re welcome! – Brian M. Scott Dec 30 '12 at 15:42
up vote 6 down vote accepted

Check out Haskell's site on Recursive function theory. That would be a good start, and you'll likely find more references as you look through the table of contents.

See also Primitive Recursive Functions 1, and Primitive Recursive Functions 2. Again, you'll find additional links to explore for clarification, as well as some suggested resources to get you on your way.

You might want to check out Boolos, Burgess, and Jeffrey's Computatibility and Logic. There's a chapter on recursive functions, starting with primitive recursive functions, and a subsequent section on recursive relations. (You can preview the text and its table of contents at the link above to see if it might meet your needs.)

You'll also find a nice pdf/handout (actually, a book chapter) from UPenn: Primitive Recursion

share|cite|improve this answer
Thanks so much for very useful suggestions! – Seraphina Dec 30 '12 at 15:40
Thanks for the tip! – Seraphina Dec 30 '12 at 15:48
Your welcome, Seraphina! – amWhy Dec 30 '12 at 15:49

Nigel Cutland's Computability: An Introduction to Recursive Function Theory is a nice gentle way into the area, although personally I found it a little slow going. Nonetheless if you want your hand held and a lot of time spent on the basics, Cutland is very good.

Once you're ready for something more rigorous and in-depth, I have to recommend Hartley Rogers's classic, Theory of Recursive Functions and Effective Computability. When you first start to read it it will seem impossibly dense, all cryptic notation and difficult ideas. But it's actually extremely well written and very clear despite its age (it dates to 1967).

As with many such books you should skip the introduction which sets out prerequisites and explains the notation: it will just slow you down and demotivate you. Instead, dive straight into the first chapter on recursive functions, which nicely motivates the problem and makes clear the key distinction between a function and a method for computing a function.

A copy should be available in any good university library, and secondhand copies can be had for very little money online. Cutland's book is also commonly assigned and so should also be available in your university library.

share|cite|improve this answer
Thanks for the excellent advice- I shall see if I can track those down! – Seraphina Dec 30 '12 at 22:49

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.