Definition
Recursion occurs when a thing is defined in terms of itself or of its type.
In computer science, recursion is a method of solving a problem where the solution depends on solution to smaller instance of the same problem.
Image explication
In this below picture, we could see several identical moments that are repeated which remain independent.
For example, we can see several times a person going up a staircase. but some times this person wears something and other times not.
Another example. We can also see a person who is waiting, sometimes upstairs, sometimes behind a table.
We can see this as a recursion in the sense that the basic action is identical but it remains particular.
Data processing recursion explication
For the purposes of this chapter, I will take a situation to explain you recursion.
Just imagine you in a cinema. You need to find your row. You could watch every row number before to find yours.
Or …
You could ask to every first sitter to verify their number until yours.
The first method is call iterative mode. The second recursive mode.
In data processing, recursion is defined when this two properties are verified:
- a final scenari
- reducing a problem to a smaller one
In our example, the final scenari is when you find your row number. The reduction of the problem is defined as you will continue to walk forward.
Example
1. float _pow_recursion(float x, float y)
2. {
3. if (y == 0)
4. return (1);
5. if (y < 0)
6. return (_pow_recursion(x, y + 1) / x);
7.
8. return (_pow_recursion(x, y - 1) * x);
9. }L. 3–4:
That our escape condition . Without these lines, the function could run like an infinite loop .
It is recommended that you first define the escape condition before writing the code for your recursive function. Like that, your sure your code will not go in infinite loop.
L. 5–6
It’s another condition. Usually not required but in our function that will be important about negative power.
L. 8
We return the common result of the function until ‘y’ retrieve the initial value (cf. following draw). The power of the number.
After this explication, you will tell me “I still haven’t figured out anything about recursion.”. That’s normal. For that, “A picture is better that 1000 words”.
Why recursion ?
Believe it or not, but some problems are easier to solve (or to read back) using recursion than they are to solve using iterative.
Take the fibonacci example.
- In iterative mode
function fibonacci(int prmNumber)
for i from 1 to prmNumber
n2 = n1
n1 = current
current = n2 + n1 return current
The Iteration method would be the prefer and faster approach to solving our problem because we are storing the first two of our Fibonacci numbers in two variables (n2, n1) and using “current” to store our Fibonacci number. Storing these values prevent us from constantly using memory space in the Stack. Thus giving us a time complexity of O(n).
2. In recursive mode
function fibonacci(int prmNumber)
if prmNumber == 0
return 0
else if prmNumber == 1
return 1 return fibonacci(prmNumber - 1) + fibonacci(prmNumber - 2)
By using Recursion to solve this problem we get a cleanly written function, that checks. If the given number is equal to 0 and 1 we return both given numbers.
recursive solution is more simular than the original function than the iterative one. Isn’t it ?
Now for a way around this would be using memorization and storing each Fibonacci calculated so.
Memory allocation
The problem with the previous example, is the memory.
Exactly. Because, when you need to calculate a number of rank 2 it’s simple. Because it does not need to perform a lot of calculation.
But when you need to calculate a number of rank 100 it’s harder, because for each number you need to calculate previous numbers. And the more you go, the more there are to calculate. It’s cascade calculation.
Conclusion
Recursion is easier to apply for some problems (understand calcul). But not at all.
Learn how to use it wisely.
Other usage: recursive acronym
Recursive acronym is an acronym that refers to itself.
Example:
PHP (Hypertext Preprocessor)
You could find more there.
Reference
GeekforGeeks. (https://www.geeksforgeeks.org/recursion/)
