through
f (x, 0) = g 1 (x),
f (x, y + 1) = h (g 2 (x, y), f (x, y)),
from defined functions g 1 , g 2 , and h.
We illustrate how this works by showing how the basic operations of integer
arithmetic can be constructed in this fashion.
Example 13.1
Addition of integers x and y can be implemented with the function add (x, y),
defined by
add ( x, 0) = x,
add ( x, y +1) = add ( x, y)+1.
To add 2 and 3, we apply these rules successively:
add (3, 2) = add (3,1) + 1
= (add (3,0) + 1) + 1
= (3+1) + 1
= 4 + 1 = 5.
Example 13.2
Using the add function defined in Example 13.1, we can now define
multiplication by
mult (x, 0) = 0,