1.Previous
3.Next

* A simple base case (or cases) -- a terminating scenario that does not use recursion to produce an answer
* A recursive step -- a set of rules that reduces all successive cases toward the base case.

For example, the following is a recursive definition of a person's ancestor. One's ancestor is either:
*One's parent (base case), or
*One's parent's ancestor (recursive step).

The Fibonacci sequence is another classic example of recursion:

: as base case 1,

:

1.Previous
3.Next