[Overview] [Previous] [Next]
If g1, g2, g3, and h are previously defined functions, we can combine them to form new functions. In a very careful, formal development, they can be combined only in precisely defined ways. Here is an example of the kind of form required.
Primitive recursion. This is a highly structured "recursive routine" with
exactly this form: f(x,0) = g1(x)
f(x, s(y)) = h(g2(x,y), g3(f(x,y)))
Note: The form of primitive recursion given in the textbook is not consistent with the author's examples. If you want to step through his (or my) examples, use this form instead.
A primitive recursive function is a function formed from the functions z, s, p1, and p2 by using only composition and primitive recursion.
Copyright © 1996 by David Matuszek
Last modified Apr 17, 1996