Understand Recursion concept the simple way

In programming, recursion concept usually daunts developers and makes them uneasy. In this post, we understand recursion concept in a simple way so that you don’t feel afraid of tackling problems using recursion.

What is Recursion?

Let’s understand recursion by means of a story.

Long long ago in a galaxy far far away…

(since THE NEW STAR WARS movie is just around the corner at the time of writing this)

A Jedi Padawan has an array of numbers. For building his lightsaber, he wants to find the odd numbers in that array. However, unfortunately no one taught him how to do it.

He asks his fellow students. But none of them also know or are unwilling to tell him. After all, they are still Padawans and therefore, prone to jealousy.

Finally, our Padawan decides to approach his Jedi Master. When he asks the Jedi Master to tell him the odd numbers in the array, the Master looks at him, smiles and answers, “I can only tell you whether the first number in an array is odd or even.”

The Padawan answers, “but Master, I need to find out all the odd numbers in the array. Only then can I build the most powerful lightsaber in the universe.”

The Master says, “That’s all fine. But I can only tell you whether the first number in an array is odd or even.”

The Padawan is left with no choice. He thinks for a moment and says, “All right”

The Discovery of Recursion

The Padawan presents the array of numbers to the Master. Below is the array:

[1, 2, 3, 4, 5]

The Master looks at the list and tell the Padawan that the first number in the array i.e. 1 is odd.

The Padawan notes it down and then provides another list to the Master as below:

[2, 3, 4, 5]

The Master gives it a glance and simply shrugs. “The first number is not odd.”

The Padawan notes it down quickly and present the next list.

[3, 4, 5]

The Master tells him that this time the first number is indeed odd.

The Padawan notes it down and proceeds with the next array.

[4, 5]

The first number is NOT odd. The Master is slightly tired now of answering the question.

The Padawan presents another list.

[5]

The Master answers that it is an odd number. Now he is visibly bored.

Finally, the Padawan presents an empty list as below:

[]

The Master, now quite bored with this game, tells him that there is no number in that list.

The Padawan heaves a sigh of relief and tells the Master that he has found all the odd numbers in the list.

The Master knowingly answer, “Indeed. But have you found something else?”

However, the Padawan, appears perplexed.

The Master smiles and replies, “Well, you have discovered the concept recursion!”

How to define Concept of Recursion?

So after going through the above story, how do you actually define recursion?

The simplest definition of recursion is a process (or a function) that calls itself.

However, there are two essential aspects of recursion that should be kept in mind:

• The Base Case – Any recursive function should have a base case. Think of the base case as an exit point to your overall process. In the Jedi’s story, the base case is reaching an empty array. Once we hit that, we basically terminate the recursive process. If there is no base case, your process can run forever and that won’t be too nice.
• Different Input for Each Call – Another important aspect of a recursive function is that in each subsequent call to itself, the input should be different. Again considering our Jedi Padawan’s case, every time the Padawan provides the list to the Master after removing the first element in the list. You can think of the different input as being a means to finally reach our base case. After that, our process ends. If we keep providing the same input, the function will never end.

Example to Understand Recursion Concept

Recursion is a concept that’s best understood by looking at examples.

Below is an example to illustrate the use of recursion by implementing a countdown timer from a base number to 0.

function countDown(num){
    if (num <= 0){
        console.log("Countdown Over!")
        return
    }

    console.log(num)

    countDown(num-1)
}

countDown(5)

In the above example, we use recursion to count down from a number to 0. Basically, we call the countDown() function within the main countDown() function. However, for each call, we reduce the value of variable num by 1. In other words, for each call, we reduce the input to our function.

The second important thing to note is our base case.

if (num <= 0){
   console.log("Countdown Over!")
   return
}

Basically, we check if the number is less than or equal to 0. Only if the number does not satisfy this check, we allow the process to go further. If we reach 0, we return from the function. Without this check, our recursive function will keep on running till the call stack size fills up.

Practical Uses of Recursion

Recursion is a very common pattern used in solving complex programming problems.

Some of the use-cases where recursion is used are as follows:

• JSON parsing algorithms
• Object Traversal in complex data structures like tree or graph. We have an example in implementing tree traversal algorithm post.
• Searching or sorting algorithms
• DOM traversal in webpages

Understanding recursion concept can help a programmer solve a wide variety of problems with efficient and clean code.