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.
Otherwise: 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.
Otherwise: 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)
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.
