Recursion

Recursion is a method where something is defined by referring to itself. In mathematics, this means that a new term in a sequence, a function, or a set depends on earlier steps. In this way, complex structures can be built up from a simple start.

 

A simple example is a recursively defined sequence:

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

The starting point is \( \large a_{0} = 1 \). Each new term is found by multiplying the previous one by 2. Thus, the first values are

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

Recursive and explicit form

A recursive formula describes a term from previous terms. Often one can also find an explicit formula, where each term can be calculated directly without knowing the previous ones. For the example above, we have

 

$$ \large a_{n} = 2^n $$

 

Recursive definitions are good at showing structure, while explicit formulas are quick for calculation. Both approaches are useful, and the two are closely connected.

 

Sequences

Recursion is used to define many well-known sequences. For example, the Fibonacci sequence, where each term is the sum of the two preceding ones.

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Functions

Another example is the factorial function. It can be defined recursively as

 

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

 

Sets

Sets can also be defined recursively. If we start by saying that 3 belongs to the set, and then add the sum of already known elements, we get all numbers divisible by 3. This can be written as a recursive definition:

 

$$ \large 3 \in M, \quad x \in M \;\Rightarrow\; x + 3 \in M $$

 

Pascal's triangle

A well-known geometric example is Pascal’s triangle. Each number is formed recursively as the sum of the two numbers above. This gives a triangular structure that contains the binomial coefficients.

 

$$ \large
\begin{array}{cccccccccccccccccc}
        &       &       &       &       &       &       &       & 1     &       &       &       &       &       &       &       \\
        &       &       &       &       &       &       & 1     &       & 1     &       &       &       &       &       &       \\
        &       &       &       &       &       & 1     &       & 2     &       & 1     &       &       &       &       &       \\
        &       &       &       &       & 1     &       & 3     &       & 3     &       & 1     &       &       &       &       \\
        &       &       &       & 1     &       & 4     &       & 6     &       & 4     &       & 1     &       &       &       \\
        &       &       & 1     &       & 5     &       & 10    &       & 10    &       & 5     &       & 1     &       &       \\
        &       & 1     &       & 6     &       & 15    &       & 20    &       & 15    &       & 6     &       & 1     &       \\
        & 1     &       & 7     &       & 21    &       & 35    &       & 35    &       & 21    &       & 7     &       & 1     \\
  1     &       & 8     &       & 28    &       & 56    &       & 70    &       & 56    &       & 28    &       & 8     &       & 1 \\
\end{array}
$$

 

 

Application

Recursion is a fundamental tool in discrete mathematics. It is used to describe infinite processes, to prove properties with induction, and to construct algorithms. In geometry, recursion also plays a role, for example in the construction of fractals.

 

Connection with induction

When working with recursive definitions, induction is a natural proof tool. One first shows that a statement holds in the base case, and then that it holds from one step to the next. In this way, one can prove properties for the entire infinite structure defined recursively.