Recursion

What is it?

Essentially is a technique that split a situation or a problem into shorter pieces of itself. Take a look at this example.

Russian dolls. At first, you see just one figurine, usually painted wood. You can remove the top half of the first doll, and after you will see another, smaller, Russian doll. You can remove that doll and separate its top and bottom halves. And you see yet another, even smaller, doll:

And again and again, and again...

Eventually, you will find the teeniest Russian doll-like a single piece if you keep going further.

So what can we conclude from this?

Easy!!!!

We will get shorter parts of the problems until we get a break condition. That in the doll's case is when this is a unique piece.

Implementation

Recursion has a lot of applications, And in this case, we'll explore how to use recursion to determine whether a word is a palindrome.

So...

A?palindrome?is a word that is spelled the same forward and backward. For example,?rotor?is a palindrome, but?motor?is not.

What we have to think about this specific problem is how can we make the problem a shorter part of itself, and after that how can we know that the problem is actually solved or not.

Notice that if we take a look at the chars from the border of the word and after starting to go to the middle, we actually can compare whether we are getting is equal or not. always comparing only 2 chars each time and not the whole word.

Next, we got an implementation in C for better understanding.

In the above code, we got a lot of words such as level, redder, test, and "step on no pets", and our mission is to realize if they are or not palindromes.

Like you can see, we are calling a function named verif implementing recursion. And what is doing the algorithm is to go from left to right and from right to left comparing if the chars in each location are the same.

If in any case result that is not, will return a 0, or on the other hand return 1 if both are found at the end and until then they are the same.

vagrant@ubuntu-focal:~/holberton/holbertonschool-low_level_programming/0x08-recursion$ ./100-palindrome
1
1
0
1?        

Recursion is a universe of solutions by itself. but at the end of the day we can conclude that is a good idea to use meanwhile we are able to think about how can the problem can be split into shorter pieces and how to know when ends the problem.

I hope that this short explanation is useful for the reader, thank you for taking the time to explore this blog.