Primitive Recursive

Primitive recursion is a weak form of recursion where one only recurses upon sub-structural elements of an input. Perhaps oddly, many non-recursive functions can be stated to exhibit primitive recursion under common definitions of the phrase.

A traditional target of primitive recursion are natural numbers expressed in Peano arithmetic s(s(s(0)))). In languages such as CharityLanguage, this is the form of natural numbers exposed to users even when, under the hood, one is still using a fixed width small integer (up to two billion or so). It is common in such languages that 'Nat' is treated as primitive and 'Int' is not.

Anyhow, short of running out of memory and stalling like a naively written Fibonacci function, PrimitiveRecursive functions are 'total'. They will always terminate. They are not TuringComplete, and enforcing primitive recursion allows one to achieve TotalFunctionalProgramming.

First order primitive recursion is insufficient to express AckermannFunction, but second order primitive recursion may do so:

  ;; Traditional formulation is not expressed primitive recursive due to recursive call on s(M)
  Ackermann   0    N  = s(N)
  Ackermann s(M)   0  = {Ackermann M 1}
  Ackermann s(M) s(N) = {Ackermann M {Ackermann s(M) N}}

  ;; Instead, define it in terms of one primitive recursive function returning another
  define Ackermann = 
   fun Ack:    0   => {fun: N => s(N)}
             s(M)  => {fun Aux:    0   => {Ack M s(0)}     ;; 'Ack' on sub-structure of its argument
                              |  s(N)  => {Ack M {Aux N}}} ;; 'Ack' and 'Aux' each recurse on their respective arguments

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

---

CategoryMath