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:
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.
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.
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:
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.
If you go to any of its children, they again have 2 children.
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:
