Recursion Explained : With real-life examples and an awesome trick

If you are a beginner in programming trying to learn the concept of recursion or someone who does understand recursion but always finds it difficult to write actual programs using recursion, then keep reading! alt text◎ Git

In this lesson, we will learn the concept of recursion in a very easy way with the help of a real-life example (rather a lame story that I wrote for you :P), and for those of you who find it hard to write recursive programs, I will tell you an awesome trick to write any recursive program like a child’s play.

What is Recursion?

Before I scare you away with those boring technical definitions that are already there in your textbooks, let’s get on with the Story of Recursion that involves Mr. Lucky and his intelligent students. At the end of the story, I promise, you will have the answer to the very question: What is recursion?

Story of Recursion

Mr. Lucky lives in his own 5 story building with his 4 intelligent students. Mr. Lucky loves their students so much that he has given each student one entire floor of the building to live on. Mr. Lucky lives on the top floor of the building and his students live on floor no. 4, 3, 2, 1 respectively. Let’s name the students by the floor on which they live. Though students are very intelligent, they are weak in maths. So, Mrs. Lucky decided to teach them how to add two numbers. All students quickly learned to add two numbers. You give them 5 + 7 and they tell the answer is 12 in no time. Everything was fine until Mr lucky decided to put their neighbor student living on floor no. 4 to a maths test and the question was follwing.

Question : Add numbers from 1 to 5, i.e. 1 + 2 + 3 + 4 + 5

After listening to the question, student 4 was clueless about how to solve this problem. He only knew how to add two numbers and not 5 of them. After thinking for a bit, he thought if he could get the sum of numbers from 1 to 4, he could easily add 5 to it and impress Mr. Lucky by telling the correct answer. In this panic situation, he secretly called his neighbor student 3 on his phone line but didn’t tell the whole situation in the fear of cheating. He asked student 3 following, “Hey how are you doing buddy? I was doing self-study of maths and I am stuck on a problem, I need to add numbers 1 to 4. Can you help me? It is kind of urgent, so I am waiting on the phone line till you tell me the answer.”

Listening to this, student 3 was also confused, since he also only knew how to add 2 numbers. He thought, “if someone could tell me the sum of numbers from 1 to 3 i.e. (1 + 2 + 3), I could easily add 4 to it and tell my friend student 4”. So he asked, “Can I put your call on hold as I think through the problem”. After putting the call on hold,

He decided to take help from student 2, he called student 2 on his phone number, he wanted to take full credit, so he did not tell the whole thing and asked the following, “Hey student 2, How are you my friend, I was just wondering if you could help me with a problem, I want to know the sum of numbers from 1 to 3, Can you please tell me quickly as I am stuck”.

Student 2 was also confused and had a similar thought, “if he could get the sum of 1 to 2, he could easily add 3 to it and impress his friend”. So he decided to take help from his neighbor Student 1 after putting the call of Student 3 on hold. He called Student 1 and said following “Hey Student 1, How are you. I have a simple problem for you, Let’s see how fast can you add the numbers from 1 to 2 i.e. (1 + 2), I am kinda stuck on this”.

Student 1 immediately realized that 1 to 2 has only two numbers 1 and 2. He applied the trick told in his maths class and came up with an answer of 3. He told the answer to Student 2 proudly hung up the phone.

As soon as Student 2 got the answer of 3, he adds 3 to it and got the sum of 1 + 2 + 3 = 6. He immediately resumed the call of Student 3 and told the answer of 6 proudly as if he only calculated the whole thing. Now it’s robot 3’s turn, He added 4 to the 6 and got the sum of 10, immediately He resumed the call of Student 4 and told the following, “So the sum of 1 + 2 + 3 + 4 is 10”. Student 4 hung up the call of Student 3 and was very happy after getting the sum of numbers from 1 to 4. It took him no time to add 5 to the given sum of 10 and finally, he got the answer of 15 and proudly presented it to Mr. Lucky. Students were able to solve this problem despite having limited knowledge of the addition of two numbers only because they were unknowingly using the concept of recursion. Some of them did not even know that they are solving a bigger problem.

Let’s take a look at what happend in the story through this image.

updatedupdated2021-02-112021-02-11