Recursion

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:

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