Defining a formal Primitive Recursion

Question

I'm searching for a way to define the function this wikipedia article call Primitive Recursion. It should have two functions as argument and it should return a function. I need this as helping in studying mathematical recursion theory. I need another help with a similar problem; this time i want a "primitive minimization", that is a function called primMin a try i made inspired by @Rojo is.

primMin[f_] := Module[{h},
    h[x___Integer] := Module[{}, For[i = 0, f[x, i] != 0, i++,]; i];
    h]

this take f a two argument function and return a one argument function that given x as an argument and search for the first second argument so that f[x,#] == 0. this code work but i couldn't find a way to substitute the For with a Map or something similar. I need that given x there is no y so that f[x,y] == 0 then program will crash or continue to run forever. thank

Answer 1

This is a sketch of a solution that only required on the fly translation from the article, done by someone who has no idea what he is doing. See if it helps (and if it works)

primRec[f_, g_] := Module[{h},
  h[0, x___Integer] := f[x];
  h[ym1_Integer, x___Integer] := With[{y = ym1 - 1},
    g[y, h[y, x], x ]
    ];
  h
  ]

I think this would be a pure function version.

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