Defining Functions by Rules
lSuppose we want to define a
function taking an arbitrary list as an argument.
lIt is
sufficient to:
ldefine the function
on the empty list, and
on the empty list, and
ldefine the function
on a general non-empty list.
on a general non-empty list.
called
the ÒbasisÓ
called the
Òinduction stepÓ or
Òinduction stepÓ or
ÒrecursionÓ