Editing Primitive recursive function (section)

=== Pure recursion ===
Another restriction considered by Robinson{{sfn|Robinson|1947}} is ''pure recursion'', where ''h'' does not have access to the induction variable ''y'':
:<math>\begin{align} f(0,x_1,\ldots,x_k) & = g(x_1,\ldots,x_k),\\
 f(S(y),x_1,\ldots,x_k) & = h(f(y,x_1,\ldots,x_k),x_1,\ldots,x_k). \end{align}</math>
Gladstone{{sfn|Gladstone|1967}} proved that this rule is enough to generate all primitive recursive functions. Gladstone{{sfn|Gladstone|1971}} improved this so that even the combination of these two restrictions, i.e., the ''pure iteration'' rule below, is enough:
:<math>\begin{align} f(0,x) & = x,\\
 f(S(y),x) & =  h(f(y,x)). \end{align}</math>
Further improvements are possible: Severin{{sfn|Severin|2008}} prove that even the pure iteration rule ''without parameters'', namely
:<math>\begin{align} f(0) & = 0,\\
 f(S(y)) & =  h(f(y)), \end{align}</math>
suffices to generate all [[unary operation|unary]] primitive recursive functions if we extend the set of initial functions with truncated subtraction ''x ∸ y''. We get ''all'' primitive recursive functions if we additionally include + as an initial function.