examples of primitive recursive functions

Starting from the simplest primitive recursive functionsMathworldPlanetmath, we can build more complicated primitive recursive functions by functionalPlanetmathPlanetmathPlanetmathPlanetmath composition and primitive recursion. In this entry, we have listed some basic examples using functional composition alone. In this entry, we list more basic examples, allowing the use of primitive recursion:

  1. 1.

    add(x,y)=x+y: add(x,0)=id(x), and add(x,n+1)=s(add(x,n))

  2. 2.

    mult(x,y)=xy: mult(x,0)=z(x), and mult(x,n+1)=add(x,mult(x,n)).

  3. 3.

    p2(x)=x2, which is just mult(x,x); more generally, pm+1(x)=mult(x,pm(x)), which is primitive recursive by inductionMathworldPlanetmath on m

  4. 4.

    expm(x)=mx: expm(0)=s(0), and expm(n+1)=mult(constm(n),expm(n))

  5. 5.

    exp(x,y)=xy: exp(x,0)=const1(x), and exp(x,n+1)=mult(x,exp(x,n))

  6. 6.

    fact(x)=x!: fact(0)=s(0), and fact(n+1)=mult(s(n),fact(n))

  7. 7.
    sub1(x)=x-˙1:={0if x=0,x-1otherwise,

    built using z and s: sub1(0)=z(0), and sub1(n+1)=s(sub1(n));

  8. 8.

    more generally, subm(x)=x-˙m may be defined: subm=sub1m.

  9. 9.

    sub(x,y)=x-˙y: sub(x,0)=id(x), and sub(x,n+1)=sub1(sub(x,n)).

  10. 10.


  11. 11.
    d0(x):={1if x=0,0otherwise.

    built using const1 and z: d0(0)=const1(0), and d0(n+1)=z(d0(n)).

  12. 12.

    more generally,

    dm(x):={1if x=m,0otherwise.

    is primitive recursive, for it is d0(diff(x,constm(x)).

  13. 13.

    even more generally,

    dS(x):={1if xS,0otherwise.

    where S={a1,,am}, is primitive recursive, for it is da1++dam.

  14. 14.
    sgn(x):={0if x=0,1otherwise.

    which is just sub(const1(x),d0(x)).

  15. 15.
    rem(x,y):={0if y=0,xmodyotherwise,

    where xmody is the remainder of x÷y. Suppose y0. Then 0mody=0. In additionPlanetmathPlanetmath,

    (n+1)mody={0if diff(s(nmody),y)=0,s(nmody)otherwise,

    Then rem(0,y)=z(y), and

    rem(n+1,y) = sgn(y)(rem(n,y)+1)sgn(|rem(n,y)+1-y|)
    = mult(sgn(y),mult(s(rem(n,y)),sgn(diff(s(rem(n,y)),y))))
    = g(y,rem(n,y))

    where g(y,x):=mult(sgn(y),mult(s(x),sgn(diff(s(x),y)))). The reason for including sgn(y) is to account for the case when y=0.

  16. 16.
    q(x,y)={quotient of x÷yif y00otherwise.

    To see that q is primitive recursive, we use equation


    obtained from the division algorithm for integers. Then


    Simplify and we get


    Thus, by the previous example, we get

    q(n+1,y)={q(n,y)+1if rem(n,y)+1=y,q(n,y)otherwise.

    Therefore, q(0,y)=z(y), and


    where sgn(y) takes the case y=0 into account.


  • All of the functions above are in fact examples of elementary recursive functions.

  • Example 3(m) above is a special case of a more general phenomenon. Recall that a subset Sn is called primitive recursive if its characteristic functionMathworldPlanetmathPlanetmathPlanetmath φS is primitive recursive. If we take S={m}, then φS=dm. Furthermore, a predicateMathworldPlanetmath Φ(𝒙) over k is primitive recursive if the corresponding set S(Φ):={𝒙kΦ(𝒙)} is primitive recursive.

  • The technique of bounded maximization may be used to prove the primitive recursiveness of the quotientPlanetmathPlanetmathPlanetmath and the reminder functions in examples 3(o) and 3(p). See this entry (http://planetmath.org/BoundedMaximization) for more detail.

Title examples of primitive recursive functions
Canonical name ExamplesOfPrimitiveRecursiveFunctions
Date of creation 2013-03-22 19:05:06
Last modified on 2013-03-22 19:05:06
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 17
Author CWoo (3771)
Entry type Example
Classification msc 03D20
Related topic ExamplesOfPrimitiveRecursivePredicates