Recursive definitions

A recursive definition is a way of describing a mathematical object by referring to itself. For such a definition to make sense, it must always include two parts:

 

• Base case: the first step(s) that start the process.
• Recursive step: a rule that explains how to form new elements from previous ones.

 

 

Functions

A classic example is the factorial function. Here are the base and recursive step:

 

$$ \large 0! = 1 $$

$$ \large n! = n \cdot (n-1)!, \quad n \geq 1 $$

 

The base specifies the value of \( \large 0! \). Then the recursive step describes how \( \large n! \) is calculated from \( \large (n-1)! \). In this way, all values of the factorial can be found step by step.

 

Example

We can compute the first values:

 

$$ \large 0! = 1 \quad \text{(base)} $$

$$ \large 1! = 1 \cdot 0! = 1 $$

$$ \large 2! = 2 \cdot 1! = 2 $$

$$ \large 3! = 3 \cdot 2! = 6 $$

$$ \large 4! = 4 \cdot 3! = 24 $$

 

Each step builds directly on the previous one, until we reach the desired value.

 

 

Functions on strings

Recursive definitions can also be used on symbol strings. An example is the function \( \large L(s) \), which gives the length of a string \( \large s \):

 

$$ \large L(\varepsilon) = 0 $$

$$ \large L(x \cdot s) = 1 + L(s) $$

 

Here \( \large \varepsilon \) means the empty string, and \( \large x \cdot s \) is a string consisting of a first symbol \( \large x \) followed by the rest \( \large s \). The base says that the empty string has length 0, and the recursive step says that the length of a longer string is obtained by adding 1 to the length of the rest.

 

 

Summary

A recursive definition is always built from a clear starting point and a rule to move forward. This division into base case and recursive step makes it possible to build complex structures in a precise and systematic way. Whether working with numbers, strings, or geometric figures, recursive definitions are a fundamental tool.