How does primitive recursion differ from "normal" recursion?

Question

I am currently reading Simon Thompson's The Craft of Functional Programming and when describing recursion, he also mentions a form of recursion called Primitive Recursion.

Can you please explain how this type of recursion is different from "normal" recursive functions?

Here's an example of a primitive recursion function (in Haskell):

power2 n
    | n == 0    = 1
    | n > 0     = 2 * power2(n - 1)

Answer 1

A simplified answer is that primitive recursive functions are those which are defined in terms of other primitive recursive functions, and recursion on the structure of natural numbers. Natural numbers are conceptually like this:

data Nat
  = Zero
  | Succ Nat -- Succ is short for 'successor of', i.e. n+1

This means you can recurse on them like this:

f Zero     = ...
f (Succ n) = ...

We can write your example as:

power2  Zero    = Succ Zero    -- (Succ 0) == 1
power2 (Succ n) = 2 * power2 n -- this is allowed because (*) is primitive recursive as well

Composition of primitive recursive functions is also primitive recursive.

Another example is Fibonacci numbers:

fib               Zero   = Zero
fib         (Succ Zero)  = (Succ Zero)
fib (Succ n@(Succ n'  )) = fib n + fib n' -- addition is primitive recursive

Answer 2

Primitive recursive functions are a (mathematician's) natural response to the halting problem, by stripping away the power to do arbitrary unbounded self recursion.

Consider an "evil" function

f n
  | n is an odd perfect number = true
  | otherwise = f n+2

Does f terminate? You can't know without solving the open problem of whether there are odd perfect numbers. It's the ability to create functions like these that makes the halting problem hard.

Primitive recursion as a construct doesn't let you do that; the point is to ban the "f n+2" thing while still remaining as flexible as possible -- you can't primitive-recursively define f(n) in terms of f(n+1).

Note that just because a function is not primitive recursive does not mean it doesn't terminate; Ackermann's function is the canonical example.

Answer 3

the recursive functions that can only be implemented by do loops are Primitive recursive functions.