Recursive Definitions

Recursive Definitions

Recursive definitions are a method for defining sets, particularly useful in computer science and mathematics. This method involves three main steps: specifying basic elements, providing rules for constructing new elements from existing ones, and declaring that only elements created through these rules belong to the set.

Basic Structure of Recursive Definitions

To illustrate recursive definitions, let’s consider the set of positive even integers, denoted as EVEN. A recursive definition for EVEN can be structured as follows:

• Rule 1: 2 is in EVEN.
• Rule 2: If x is in EVEN, then x + 2 is also in EVEN.
• Rule 3: The only elements in EVEN are those that can be produced from the two rules above.

In this definition, Rule 1 establishes the base case, while Rule 2 allows for the generation of new elements. Rule 3 asserts that no other elements are part of the set.

Working with Recursive Definitions

To prove that a specific number belongs to the set defined recursively, you can apply the rules step by step. For example, to show that 14 is in EVEN, you would proceed as follows:

By Rule 1, 2 is in EVEN.
By Rule 2, 2 + 2 = 4 is in EVEN.
By Rule 2, 4 + 2 = 6 is in EVEN.
By Rule 2, 6 + 2 = 8 is in EVEN.
By Rule 2, 8 + 2 = 10 is in EVEN.
By Rule 2, 10 + 2 = 12 is in EVEN.
By Rule 2, 12 + 2 = 14 is in EVEN.

Advantages of Recursive Definitions

Recursive definitions can be advantageous because they allow for concise proofs of properties about the set. For instance, using the second recursive definition of EVEN, it is straightforward to prove that the sum of any two even numbers is also even:

Proof: Let x and y be elements of EVEN. By Rule 2, x + y is in EVEN.

This property may be more complex to prove using non-recursive definitions.

Examples of Recursive Definitions

1. **Positive Integers:** The set of positive integers, INTEGERS, can be defined recursively as:

• Rule 1: 1 is in INTEGERS.
• Rule 2: If x is in INTEGERS, then x + 1 is also in INTEGERS.

2. **Polynomials:** A polynomial can be defined recursively as:

• Rule 1: Any number is in POLYNOMIAL.
• Rule 2: The variable x is in POLYNOMIAL.
• Rule 3: If p and q are in POLYNOMIAL, then so are p + q, p - q, and p * q.

For example, to show that the polynomial 3x² + 7x - 9 is in POLYNOMIAL, you would use the following steps:

By Rule 1, 3 is in POLYNOMIAL.
By Rule 2, x is in POLYNOMIAL.
By Rule 3, (3)(x) is in POLYNOMIAL; call it 3x.
By Rule 3, (3)(x)(x) is in POLYNOMIAL; call it 3x².
By Rule 1, 7 is in POLYNOMIAL.
By Rule 3, (7)(x) is in POLYNOMIAL.
By Rule 3, 3x² + 7x is in POLYNOMIAL.
By Rule 1, -9 is in POLYNOMIAL.
By Rule 3, 3x² + 7x + (-9) = 3x² + 7x - 9 is in POLYNOMIAL.

Recursive Definitions in Real-World Contexts

Recursive definitions are not only confined to mathematics but also appear in everyday situations. For example, consider the descendants of a person:

• Rule 1: The children of a specific person are members of the set of descendants.
• Rule 2: If x is a member of descendants, then x's children are also members of descendants.

This method of defining descendants is recursive because it refers back to itself.

Recursive Definitions in Computer Science

In computer science, a procedure that calls itself is referred to as recursive. This self-referential nature is similar to the recursive definitions we have discussed. For instance, a function to calculate the factorial of a number n can be defined as:

factorial(n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Conclusion

Recursive definitions provide a powerful way to define sets and properties. They are particularly useful in proving theorems and properties within mathematics and computer science.

Check your understanding

• Define the set of odd integers using a recursive definition.
• Using the recursive definition of EVEN, explain how you would prove that 100 is in EVEN.
• What are the advantages of using recursive definitions over non-recursive definitions?
• Provide a recursive definition for a new set of your choice.