How to use Recursion to Reverse a String in JavaScript
In this article, we will learn how to reverse a string using recursion in JavaScript. Firstly, we need to understand recursion, and what will be its role in reversing the string.
Note: If you are already aware of recursion, you can skip the “What is recursion” section of the article, and read the “Reversing a string overview” section.
What is recursion?
Recursion is when a method calls itself until a terminating condition is met. Let us understand it using an example.
Example
We have a function: add(n). This function will add all numbers from and including n down to 1. If n is 4, the result returned by the add function would be 4 + 3 + 2 + 1 = 10.
function add(n){
if(n == 1){
return 1;
}
else {
return n + add(n - 1) //the function calls itself.
}
}The above function uses recursion as it calls itself.
Explanation of the above function
The add() function might be way confusing at first. Hence, to understand it perfectly, let us create a trace table showing the function call: add(4)
When the function is executed for the first time, n is 4. The if statement is false, hence the function returns n + add(n - 1) that is 4 + add(3). Next, the function add(3) is called and n now becomes 3. The if statement is false, therefore, the function returns n + add(n - 1) that is 3 + add(2). We can visualize the first return statement as: 4 + (3 + add(2)). Next, the function add(2) is called and n now becomes 2. The if statement is false, therefore, the function returns n + add(n - 1) that is 2 + add(1). We can visualize the first return statement as: 4 + (3 + [2 + add(1)]). Again, the function add(1) is called and now n becomes 1. The if statement is true, therefore the function returns 1 . We can visualize the first return statement as: 4 + (3 + [2 + 1]). The answer to the first return statement is 4 + 3 + 2 + 1 = 10 Hence 10 is returned by the original function call: add(4)
Reversing a string
A reversed string is a string in its reversed form. For example, we have a string, “reverse”. The reverse of this string would be: “esrever”. Well, there are some strings that when reversed, look and are the same as the original string. For example, the string, “lol”. Its reverse is also: “lol”!
We will thus reverse strings using recursion in JavaScript. Let us visualize, how will we actually reverse the string.
At first, we will create a function called reverse()
function reverse() {}The function reverse() will be used to reverse the string. We will pass a parameter to the function, to receive the string.
function reverse(str) {}For reversing the string, we need to take the last character of the string and make it the first character. Therefore, we can use the length property and the charAt() function to retrieve the last character.
return str.charAt(str.length - 1);The above code can be used to retrieve the second-last value also! How does this happen? We can substring the last character of the string; therefore, the second-last value becomes the last value.
Example: “Test”: “Test”.substring(0, “Test”.length) = “Tes”
str.charAt((str.substring(0, str.length - 1).length) - 1);The above code gives the position of the second last character. Therefore the return statement becomes:
return str.charAt(str.length - 1) + str.charAt((str.substring(0, str.length - 1).length) - 1);Therefore, the reverse() function code is:
function reverse(str) {
return str.charAt(str.length - 1) + str.charAt((str.substring(0, str.length - 1).length) - 1);
}If we execute reverse(“Test”) , we get the value: ts. This is not correct, as we wanted the reverse of “Test”, which is “tseT”. So, what is missing?
Well, did we use recursion? No! Recursion is missing. Hence the code did not execute multiple times to return the reversed string.
What condition should we add to make the function recursive? Well, if we look carefully we see that the length of the string changes (substring removes the last character, and hence the length changed by 1). Hence, we can use the length of the string to terminate the recursive function.
if(str.length <= 1){
return str;
}else {
return str.charAt(str.length - 1) + str.charAt((str.substring(0, str.length - 1).length) - 1);
}
The above code can now be added to the function reverse()
function reverse(str){
if(str.length <= 1){
return str;
} else {
return str.charAt(str.length - 1) + str.charAt((str.substring(0, str.length - 1).length) - 1);
}
}
If we execute reverse(“Test”) , we get the value: ts . This is not correct, as we wanted the reverse of “Test”, which is “tseT”. So, what is missing?
Again… Where is recursion? We just added the terminating condition, but where are we calling the reverse() function again?
Let’s add the reverse() function in the return statement. Logically, the reverse function returns the last two characters. We can call the reverse function again in the return statement like this:
function reverse(str){
if(str.length <= 1){
return str;
}
else {
return str.charAt(str.length - 1) + reverse(str.substring(0, str.length - 1));
}
}The return statement: return str.charAt(str.length — 1) + reverse(str.substring(0, str.length — 1)); returns the last character and calls the reverse function again with a new string. The new string is the one whose last character was removed through the substring function. Now, let’s visualize this recursive call through an example.
Visualizing the reverse function
Let’s take an example. We call the function reverse() with the string: “Test”.
When the function is executed for the first time, the str is "Test". The if statement is false, hence the function returns str.charAt(str.length — 1) + reverse(str.substring(0, str.length — 1)); that is "t" + reverse("Tes"). Next, the function reverse("Tes")is called and str now becomes “Tes”. The if statement is false, therefore the function returns "s" + reverse("Te") .
We can visualize the first return statement as: "t" + ("s" + reverse("Te")) . Next, the function reverse("Te")is called and str now becomes “Te”. The if statement is false, hence the function returns "e" + reverse("T"). We can visualize the first return statement as: "t" + ("s" + ["e" + reverse("T")]).
Again, the function reverse("T")is called and now str becomes “T”. The if statement is true, therefore the function returns "T". We can visualize the first return statement as: "t" + ("s" + ["e" + "T" ]). The answer to the first return statement is "t" + "s" + "e" + "T" = "tseT" Hence “tseT” is returned by the original function call: reverse(“Test”).
reverse function.Here is a simple visualization of how the recursive function would actually work:
Testing the above function
Let us test the function. Here are some test cases: Recursion, JavaScript.
Input: Recursion Input: JavaScript
Output: noisruceR Output: tpircSavaJThe function works perfectly!
The final code:
Conclusion
Thank you for reading this article. I hope you have found it useful. If so, be sure to leave a comment to let me know.
More content at plainenglish.io
