How can the basic primitive recursive functions be expressed in the Wolfram Language?

Apparently here's an example for primitive recursion:

prRec[f_, g_] :=If[#1 === 0, f[##2], g[#1 - 1, #0[#1 - 1, ##2], ##2]] &

The basic primitive recursive functions are:

  • Zero function $0$
  • Successor function $S(k) = k + 1$
  • Projection function $\pi_i(x_1,\ldots,x_i,\ldots)=x_i$
  • Composition
  • Primitive recursion
  • 1
    $\begingroup$ Could you expand the question a bit? Specifically, state how the included example fails to answer the question, and how the question is different from the one you linked. $\endgroup$ Jan 28, 2016 at 21:21
  • $\begingroup$ @SimonWoods That one was specifically for the primitive recursion operator. $\endgroup$
    – user76284
    Jan 28, 2016 at 21:23
  • 5
    $\begingroup$ When early H. Sapiens painted pictures of themselves painting on cave walls, was that primitive recursion? $\endgroup$ Jan 28, 2016 at 21:30
  • 1
    $\begingroup$ Related: (1532) $\endgroup$ Jan 28, 2016 at 22:15
  • 1
    $\begingroup$ Steven W. takes crack at defining primitive recursive functions in M here:wolframscience.com/nks/notes-4-3--primitive-recursive-functions $\endgroup$
    – Rabbit
    Feb 28, 2018 at 20:11

1 Answer 1


Some of these could be implemented differently, of course, but I've gone the way of making all of them pure functions (in the Mathematica sense). Every single one takes a Sequence of arguments as the inputs, but some of them accept function names as inputs first, and the projection function accepts an integer for which argument is chosen (I have chosen to use Mathematica indexing which starts at one).

  • Zero function

    zero = 0 &;
    (* 0 *)
  • Successor function

    succ = # + 1 &;
    succ /@ Range[10]
    (* {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} *)
  • Projection function

    proj[n_Integer] = {##}[[n]] &;
    proj[3][a, b, c, d]
    (* c *)


    proj[n_Integer] := Slot[n] &
  • Composition

    comp[f_, gs__] = f @@ Through@{gs}@## &;
    comp[f, g1, g2, g3][a, b, c, d, e]
    (* f[g1[a, b, c, d, e], g2[a, b, c, d, e], g3[a, b, c, d, e]] *)
  • Primitive Recursion: with this one, you need to be careful. It assumes that the first argument is a non-negative integer. If it is not, there will be an infinite recursion.

    prec[f_, g_] = If[#1 == 0, f[##2], g[#1 - 1, #0[#1 - 1, ##2], ##2]] &;
    prec[f, g][3, x, y, z]
    (* g[2, g[1, g[0, f[x, y, z], x, y, z], x, y, z], x, y, z] *)

Possible issue, based on my lack of knowledge about how this is implemented. The successor function seems to be what is used to decrement arguments to the function in order to define things recursively. For instance, the binary add function can be implemented via

add[0, x_] := proj[1][x]
add[n_, x_] := succ[proj[2][n - 1, add[n - 1, x], x]]

but it cannot be implemented via

add[0, x_] := proj[1][x]
add[succ[n_], x_] := succ[proj[2][n, add[n, x], x]]

which is the official definition of the primitive recursive binary sum function in terms of the basic primitive recursive functions.

  • $\begingroup$ How would you express the add function directly in terms of prec? $\endgroup$
    – user76284
    Feb 1, 2016 at 17:19
  • $\begingroup$ @user1667423. I don't know. Do you know how it's done "formally"? That is, if you have a link to something that shows how to do it symbolically (similar to what's done on the Wikipedia page on primitive recursion, which is basically what I used to learn about this), then I can probably interpret it in terms of the Mathematica language. Otherwise, you should probably do some of this work yourself. $\endgroup$
    – march
    Feb 1, 2016 at 17:24
  • $\begingroup$ Ah, I found the answer under en.wikipedia.org/wiki/Primitive_recursive_function#Addition. So f is proj[1] and g is comp[succ, proj[2]] in add = prec[f, g]. Thanks for your help with this question! $\endgroup$
    – user76284
    Feb 12, 2016 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.