Recursive definition

A recursive definition consists of a base case that does not use recursion, and a recursive step that reduces any successive case toward the base case. Sequences, sets, and functions can be defined in this way.

For example, factorials and the Fibonacci sequence are both capable of being recursively defined.

Recursively defined sets

Some sets are most intuitively defined through recursion, in which any arbitrary element can be assembled from simpler elements. These definitions will always include:

1. A base case, which explicitly lists off one or more specific elements that are in the set.
2. A recursive rule, which shows how to build additional elements from elements already in the set.
3. An exclusion statement, which claims that for any element to be a part of the set, it must either already be in the base case, or be capable of being built through repeated application of the recursive rule on elements in the base case. Since this statement is the same for every recursively defined set, it is often omitted, because it is implied.

For example, the set of all binary strings, \(B^*\), can be recursively defined:

Naturally, any binary string you can imagine can be built by starting with the empty string, \(\lambda\), and repeatedly concatenating \(0\) or \(1\) to the end of it. To build \(1001\) for example, the process would be: \(\lambda \rightarrow \lambda 1 = 1 \rightarrow 10 \rightarrow 100 \rightarrow 1001.\)

Actually, it's also possible to recursively define the length function of a binary string in a very similar manner:

Of course, this definition requires that \(B^*\) is already defined. If it is, then, the length of every binary string can be determined by counting the number of concatenations that were made to the empty string \(\lambda\) in order to build it.