# Defining a formal Primitive Recursion

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

-
Hello! What have you tried, where are you getting stuck, and etc etc? (Typical questions so we feel enablers of your MMA learning and not unpaid employees ) – Rojo Jan 21 '14 at 2:04

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]] &

-
This is exatcly what i needed my problem were i hadn't familiarity with function like With or Module, I will be testing this and eventually report any misbehavior if any – KiriaKasis Jan 21 '14 at 13:22