Recursion, demystification

Métamorphose du monde — Maurice Cornelis Escher

Definition

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 .

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, “”.

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.

  1. 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

Example:

PHP (Hypertext Preprocessor)

You could find more there.

Reference

GeekforGeeks. (https://www.geeksforgeeks.org/recursion/)