Recursive Definitions

Everyday Examples

Royalty: A person is royal if is a monarch or is descended from a royal person.
Citizenship: A person is a canadian citizen if he was born in Canada, or has acquired citizenship after emigrating to Canada, or has a parent who is a Canadian citizen.

Mathematical Examples The factorial function:

factorial(0) = 1
factorial(n) = n * factorial(n-1) [for n>0]

Let's compute factorial(3):

factorial(3) = 3 * factorial(2)
             = 3 * ( 2 * factorial(1) )
             = 3 * ( 2 * ( 1 * factorial(0) ))
             = 3 * ( 2 * ( 1 *      1     ) ))
             = 6

Recursive Definition: base case(s) + recursive case