Informally speaking, a recursive definition defines something (e.g., a
function or a procedure) in terms of itself (but not in such a way to
create an unending process!). For example, we can
define the function *f*(*n*) for *n*! the following way:

Often definitions or descriptions by recursion lend themselves to proofs by induction.

Here is another example, for the Towers of Hanoi. We define the
procedure move(*n*,*a*,*b*,*c*) for moving a stack of disks numbered
from peg *a* to peg *b* using peg *c*:

- If
*n*>1 then move(*n*-1,*a*,*c*,*b*). - Move disk
*n*from*a*to*b*. - If
*n*>1 then move(*n*-1,*c*,*b*,*a*).

Wed Apr 21 08:17:28 EDT 1999