The principle of defining the value of a function recursively is very close to the principle of mathematical induction. The method is quite straightforward.

1. Specify the value of a function, f, at some base value, K
2. Specify the value of f(N) in terms of f(I) where K <= I < N

Example

The function FT is defined as follows:

FT(0) = 1

FT(N) = N· FT(N-1)

As one will readily see FT is the familiar factorial function

Numerous other examples are given in the text.

 

Recursively Defined Sets

Recursive definitions are not restricted to functions. Other objects such as sets may be defined recursively as well.

Example:

Define the set of positive, odd integers, ZO, recursively.

1. 1 Î ZO
2. If x Î ZO Then x + 2 Î ZO