In some programs we need to get a result that consists on repeating the same algorithm certain amount of times. For obtaining the result we need to obtain the result of the same problem in smaller instances.
For example:
We want to obtain the result of certain number raised to another number. This is the same as multiplying the first number by itself during the second number of times.
But also, this is the same as multiplying the first number times the first number raised to second number minus 1.
For example:
5^3 is the same as:
5*5*5
Which is the same as:
5*5^2 which is the same as: 5*5*5^1 which is the same as 5*5*5*5^1
Now we just need to know what 5^1 is equal to.
What we just did is what we call recursion. We want to obtain the result of a problem by solving the same problem in smaller instances. It can be applied to code in this way:
And it gives us the same answer:
Another example is a number in the Fibonacci series.
This series start with the value “0”, followed by “1”. After that, every number is equal to the sum of the two previous numbers. This means that the third number will be equal to 0+1 which is 1. And the fourth number will be 1+1 which is 2.
This can be solved used recursion.
If we get asked for the tenth number in the Fibonacci series, this will be the sum of the ninth and the eight numbers.
And the ninth number is the sum of the eight and the seventh.
The eight is the sum of the seventh and the sixth…
And so on until we get to the first two number, that are the ones that we actually know.
Here is the series so you can prove the answer is correct
( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 )
Recursion by Frida Diaz is licensed under a Creative Commons Attribution 4.0 International License.