[Overview] [Previous] [Next]

Composition and Recursion

If g₁, g₂, g₃, 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.

• Composition: f(x,y) = h(g₁(x,y), g₂(x,y)).
  This lets us use functions as arguments to functions.
  

• Primitive recursion. This is a highly structured "recursive routine" with exactly this form: f(x,0) = g₁(x)
  f(x, s(y)) = h(g₂(x,y), g₃(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.