In this tutorial, we will learn the concept of recursion with two examples. In the first example, we will sum the numbers until the given one and in the second example, we will check if our string is a palindrome.
1. What is Recursion?
Recursion is an effective technique for solving complex problems in Computer Science.
Recursion invokes what we define. In an iterative function definition in the function body, we call the function we defined, that is, there is a recursion loop [1].
We can generate many recursive calls as needed. However, we must provide a certain state to end this iteration process. We can say that the function calls itself each time with a simpler version of the original problem [2].
2. Examples of recursive functions
When we try to solve recursive problems, we often use a two-step process. The first step is to determine the base case, and the second is to determine the recursive case.
We can solve the base case directly, which means we don't need to call the function or do anything else. The recursive case, however, can be solved by taking part of the problem and then recursively solving a sub-problem that is quite similar to the original problem.
2.1 Sum all numbers until the given one
In the first example, we will sum the numbers until the given one. In the figure below (Figure 2.1), we can see that the function S( ) itself is called inside the function, so this phenomenon is called "recursion", and the function which contains recursion is named a "recursive function".
Figure 2.1 Mathematical approach
function SumupTo(n) {
if (n === 1) {
//base case
return 1;
} else {
// recursive case
return n + SumupTo(n - 1);
}
}
document.write(SumupTo(2)); // output = 3
document.write(SumupTo(3)); // output = 6
document.write(SumupTo(5)); // output = 15
document.write(SumupTo(10)); //output = 55
2.2 Check whether the string is palindrome or not
In the second example, we will learn to write a recursive function to check if a string is a palindrome.
What is the string palindrome? This means that the original string and its inverse are equal (i.e., madam, dad, …).
Firstly, we will determine the base case. We can easily say that if the length of the string is only one, it must be a palindrome. If the length is zero, it also must be a palindrome. So, if the string length is less than 2, we will return true.
function isPalindrom(string) {
if (string.length < 2) {
// base case
return true;
}
}
We are now in the recursive case, so we will check if the first and last letters are the same. We will use another if … else statement inside the else statement. If the first and last letters are not equal, we will return false.
function isPalindrom(string) {
if (string.length < 2) {
// base case
return true;
} else {
// recursive case
if (string[0] !== string[string.length - 1]) {
return false;
}
}
}
Otherwise, if the first and last letters are equal, we will call the function again. We have already checked the first and last letters, so we do not need to check them again. We can remove these letters using the slice() method.
The slice() method extracts a part of a string and returns the extracted one. For easy understanding, we can give a simple example of the slice() method. As we can see in the example below, we have removed the first and last letters.
let myStr = "Hello";
console.log(myStr.slice(1, -1)); // output = ell
Now we can get back to our recursive function. Our code will be like this:
function isPalindrom(string) {
if (string.length < 2) {
// base case
return true;
} else {
// recursive case
if (string[0] !== string[string.length - 1]) {
return false;
} else {
return isPalindrom(string.slice(1, -1));
}
}
}
Finally, our code is ready to check whether our strings are palindrome or not.
function isPalindrom(string) {
if (string.length < 2) {
// base case
return true;
} else {
// recursive case
if (string[0] !== string[string.length - 1]) {
return false;
} else {
return isPalindrom(string.slice(1, -1));
}
}
}
document.write(isPalindrom("dad")); // output: true
document.write(isPalindrom("gulcan")); // output: false
document.write(isPalindrom("madam")); // output: true
3. Conclusion
In this tutorial, we first learned what recursion and recursive functions are. Then we tried to add the numbers until the given one by using the recursive function. We also checked if our strings are palindrome using recursion concept.
These are simple algorithms to understand the concept of recursion, we can solve other algorithms using recursive functions.
👋🏼 Happy learning …
You can reach out to me through LinkedIn and Medium
Top comments (0)