Home Theory Algorithmic Paradigms – Recursion

Algorithmic Paradigms – Recursion

by nikoo28
0 comment

The first thing that comes to our mind on hearing the word recursion is doing a thing over and over again. But how can you expect to achieve a solution to a problem by repeating the same thing over and over again. In this post we would be understanding exactly that. Algorithmic paradigms are a way to solve a problem, and recursion is one of them. Some of the other ways are:

So, what is Recursion?

Sometimes a good image helps to understand things better as they stick in our mind. Have a look at this example:

gif showing recursion
GIF: Recursion in TV

So, what is happening in the image? The father(Homer) is showing his kid(Bart) an image which he is again showing an image. As we keep zooming in, we would see a repetitive pattern. This is called recursion.

Even google has a hidden Easter egg when it comes to recursion. Try searching the term recursion, and even though you spell it correctly. Google will suggest you a correction.

google Easter egg
GIF: Hidden google Easter egg

Even if this does not clear your mind, have you ever tried looking at two mirrors that stand parallel to each other? You see a lot of images of yourselves.

figure showing recursion in mirrors
Fig: Recursion in parallel mirrors
How does this apply in Computer Science?

These are all examples of infinite recursion. That means the series just goes on an on. We need to find a way to leverage this repeating feature and somehow try to solve a problem using this approach. If we are able to stop at a certain point during this repetition, maybe we can derive some result from it.

Before starting with an example note that, not all problems can be solved using recursion. We need to first identify if recursion can even be used. Example, if I ask you to find the maximum number in an array, then it does not follow a repeating property.

Problems involving Recursion

A very famous problem that involves the concept of recursion would be to calculate the factorial of a number. The factorial of a number is given as:

n! = \begin{cases} 1, & \text{if $n = 0$}.\\ n * (n-1)!, & \text{if $n > 1$}. \end{cases}

Going by the above formula, if we have to calculate 5!. It would be given by

5! = 5 * (5-1)!
OR
5! = 5 * (4!)

Now, we would need to calculate 4!, which would be given by
4! = 4 * (3!).

Properties of a Recursive Problem

What we see here is a repetitive or a recursive property. As we just discussed above, we can take advantage of recursion if we can reach a stopping point. All the factorials end at 1.
5! = 5 * 4 * 3 * 2 * 1
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Thus, we can say that for a problem to be solved using recursion it should have a terminal condition. Another example that you may think is Binary Search. We keep on applying the same technique to a smaller section of an array, until we reach a stopping point (i.e, the number will be found/not found).

This tells us another important property about recursive problems. The smaller problem formed from the bigger one should be similar to the original problem. When we calculate 5! we do 5 * 4 * 3 * 2 * 1

Here 4 * 3 * 2 * 1 is equivalent to 4!, hence we can say 5! = 5 * 4!

Thus, the smaller sub-problem has the same structure as the original problem. Think of a binary tree, the root node has 2 children left-tree and right-tree.

figure showing structure of binary tree
Fig: Binary tree showing root, left and right tree

If you go to any of its children, they again have 2 children.

figure showing recursive property in binary tree
Fig: Recursive property in a Binary Tree

This follows a pattern for recursive problems. Hence, you will find that a lot of tree traversal problems can be solved easily using recursion.

Further Reading:

If you would like to know more about problems that use recursion here are some famous examples:

Video Explanation:
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More