Recursion: what is it?

Recursion definition

Recursion is a mathematical concept that defines a process of successive repetitions for a given phenomenon. As simply as possible, recursion can be understood as therepetitive execution of a procedure. When the process of solving a problem consists of several repetitions of the same procedure.

Here’s a classic example of recursion, the droste effect:

The droste effect defines an image that is formed by successive repetitions of itself.

Another example, observable in the real world, is the recursion of reflections between parallel mirrors:

When two mirrors are placed in parallel, a series of repetitions of their reflexes are formed recursively.

To begin to understand the meaning of recursion, let’s look at some examples of activities being recursively resolved.

The activity of digging a 1m deep hole

Note that a digging activity consists of repeating the same set of steps until a “1m deep” condition is reached!

The activity of cleaning the floor of a room

Note that the activity of cleaning the floor of a room also consists of successively repeating the same set of steps until the “no dirty regions” condition is reached!

Note that these activities are performed as a sequence of steps that end by restarting the cycle. That is, at the end of the activity, everything is repeated again.

Example of recursion issues

Let’s see in practice the real situations in which the concept of recursion applies:

Recursion in the construction of Sierpinski’s triangle

The Sierpinski triangle is a fractal geometric figure. Its construction is given by a recursive process of dividing triangles into smaller triangles. Notice below an illustration that shows what the Sierpinski triangle is.

Step 1

Step 2

Step 3

Step 4

Notice how it is constructed by repeating the same procedure: dividing a triangle into three other pieces:

Whole triangle

We subdivided the triangle

Resulting pieces

Once the triangle has been split, the construction process continues for each of the 3 new pieces resulting from the previous step.

Three pieces resulting from the previous step

Each subdivides again into 3 other pieces

Resulting pieces

Notice below an animation of this subdivision process.

Notice how the construction of the Sierpinski triangle is a problem where recursion is present. Its construction boils down to the repetition of the same triangle subdivision procedure.

Recursion in the Factorial Number

Another problem that has a recursive nature is Factorial, which is represented by the symbolism “n!”. Thus the factorial of 5 is symbolized as “5!”.

The factorial is calculated by the product of consecutive integers between 1 and n. See the examples:

The recursive nature of the factorial number is that it is given by multiplying the value n by its predecessor and this happens consecutively. It could be represented as follows:

Thus, the factorial calculation of a number comprises in a series of steps of factorial calculation of a decreasing number.

Note in the example above that the calculation is a repeated sequence of the same procedure.

Recursion in the Fibonacci Sequence

The Fibonacci sequence is a sequence of numbers as follows:

It may seem like just a random sequence of numbers, but the sequence has a very interesting rule that defines its formation: except for the first two values, the values are formed by the sum of their two predecessors.

Notice, in the sequence below, how the value 2 is formed by the sum of the two predecessors (1 and 1).

Similarly, the value 3 is formed by the sum of 2 plus 1.

The value 5 is formed by the sum of 3 plus 2.

The value 8 is formed by the sum of 5 plus 3.

The value 13 is formed by the sum of 8 plus 5.

The recursive nature of the Fibonacci sequence is that the nth term of the sequence is found as follows:

Thus, the calculation of the 5th term of the Fibonacci sequence is performed as follows:

Note in the example above that the calculation of the nth Fibonacci term is a repeated sequence of the same summation procedure of its two predecessors.

One area where recursion is widely used is Computer Science. In it, the concept is used for the implementation of Recursive Algorithms. Click this link and visit the article where we explain in detail about Recursive Algorithms.