Recursion: what is it?

Understand the meaning of the mathematical concept of recursion and see some examples of real problems where it is applied.

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

Spike the hoe into the soil

Step 1

Remove an amount of land

Step 2

Put the set aside land in another region

Step 3

Did the hole reach 1m deep?
If so:
 finish the task.
go back to step 1.

Step 4

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

Soak the cloth in water

Step 1

Wring the cloth

Step 2

Wipe the cloth over a small soiled area

Step 3

Are there still dirty regions?
If so:
go back to step 1.
finish the task.

Step 4

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:

5! = 5×4×3×2×1 = 120
4! = 4×3×2×1 = 24
3! = 3×2×1 = 6

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:

n! = n × (n-1)! : Factorial of n is equal to n multiplied by Factorial of n minus 1.

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

4! = 4 × (3)! : Factorial 4 is equal to 4 multiplied by Factorial 3.
3! = 3 × (2)! : Factorial 3 is equal to 3 multiplied by Factorial 2.
2! = 2 × (1)! : Factorial 2 is equal to 2 multiplied by Factorial 1.
1! = 1 : Factorial of 1 is always equal to 1.

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:

fib(n) = fib(n-1) + fib(n-2)

That is: the nth term is equal to the sum of the previous two.

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

fib(5º) = fib(4º) + fib(3º).
fib(4º) = fib(3º) + fib(2º).
fib(3º) = fib(2º) + fib(1º).
fib(2º) = 1.
fib(1º) = 1.

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.

David V. Santiago

David V. Santiago

MSc in Systems and Computing, Professor of Computer Programming, Algorithms and Data Structures.

Was this article helpful to you?

So support us and share it with others who are interested in this subject!

Share on whatsapp
Share on facebook
Share on twitter
Share on linkedin
Share on email

Follow us
on our social media.

This website uses cookies to ensure you get the best experience on our website.