tags:

views:

562

answers:

4

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)
+1  A: 

http://en.wikipedia.org/wiki/Primitive_recursive_function

John Millikin
...so very helpful -_-
Andreas Grech
Would you rather I copy-paste some sections of it? If there's some aspect of primitive recursion that you don't understand, a better answer can be provided, but "how does it differ from general recursion" can be answered merely by looking at the definition in Wikipedia.
John Millikin
The OP is trying to learn something here. Would you refer your students to an encyclopedia if you were a math teacher?
Wim Coenen
@wcoenen The OP was essentially asking for a definition of primitive recursion. That article has the definition. If the OP is confused about the definition he should ask a more specific question.
Captain Segfault
I'm asking for a "simple" explanation, not a definition.
Andreas Grech
+4  A: 

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.

Captain Segfault
+5  A: 

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
Porges
A: 

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

sathishkumar
Just FYI (based on your other post, not this one) , you can post a CV at http://careers.stackoverflow.com/
Bill the Lizard