One of the most important concepts in computer science for new students/developers to learn is recursion. This is at the heart of a lot of practical and useful algorithms that can help us solve problems clearly and concisely. When learning how to program, students start with iteration or loops to get the answer. Nevertheless, recursion might solve the problem in a more elegant way with less code and easier to understand.
In this article, we are going to cover recursion using JavaScript in the examples. However, the concept itself applies to all modern programming languages.
First, it is necessary to define recursion to have an idea of what it is. Recursion is when a function calls itself by solving parts of a larger problem until solving the larger problem and its totality. Or the recursion definition provided by Malik (2013) as “the process of solving a problem by reducing it to smaller versions of itself”.
Another way to see a recursion is like a loop of a function calling itself from inside the function body until it reaches a point of returning the value. As the simplest version for the sake of explanation, a recursive function would be like the following:
function recursion() {
recursion();
}
Calculating the Factorial n!
The factorial is the product of all the positive integers that are less or equal to n. To illustrate, 4! = 4 * 3 * 2 * 1 = 24. But, the factorial of zero is one 0! = 1. Thus, if you are trying to find the factorial of zero, the value will be one and not zero. This is a good example because it is simple enough to grasp what could be solved with a recursive function.
The first step is to get the base case which is the value that will be returned directly from the function. For our factorial function, the base case is when n is one or zero, it will return 1. Thus, if we use factorial(1) or factorial(0), one will be returned by the function.
Then, the general case is the one that must be solved recursively. The general case for the factorial function is multiplying the current number with the number returned by the factorial function.
function factorial(n) {
if(n <= 1) return 1;
return n * factorial(n - 1);
}
The following is an illustration of what is happening when calling factorial(4).
Where and When Recursive Functions Can Be Used
Before document.getElementsByClassName there was a need to select elements based on their class names. I remember creating a recursive function that went deeper if the element had children. Another example is the recursive function that will open folders recursively and display their content. But, recursion is bigger than just playing with HTML, JavaScript, and listing directories. With recursion, it is possible to create elegant solutions that replace iterations.
Recursion is handy for popular algorithms like binary search because it provides a more elegant solution than the iterative version. In addition, programming puzzles like sudoku can be solved using backtracking, which uses recursivity to guess the number of each puzzle cell. If you apply for a software development job, at least one of the coding questions in the interview will be related to recursion.
Other Recursive Functions for Practice
Counting Down
Prints a count down on the console from n to zero.
function countDown(n) {
if (n === -1) return;
console.log(n);
countDown(n - 1);
}
Palindrome
Verifies if a string is a palindrome. Thus, the string should read the same when backwards.
function isPalindrome(str) {
if(str.length <= 1) return true;
return str.substring(0,1) === str.substring(str.length - 1) ? isPalindrome(str.substring(1, str.length - 1)) : false;
}
Reverse
Reverses a string.
function reverse(str) {
if(str.length == 1) return str;
return str[str.length - 1] + reverse(str.substring(0, str.length -1));
}
JavaScript Only Information
In JavaScript, a property within the function is part of the arguments object called callee which represents the current function. Thus, instead of calling factorial within the factorial function, you could use arguments.callee. This is an ancient approach and it is not recommended today. If you use this in strict mode, it will return an error.
function factorial(n) {
if(n <= 1) return 1;
return n * arguments.callee(n - 1);
}
Conclusion
In conclusion, recursion is important for anyone that has serious aspirations to become a programmer. Also, don’t think of recursive algorithms as language-dependent because they are more of a way to think in order to solve a problem. The concepts of recursion apply to most popular programming languages and it has become second nature in solving complex problems. Finally, you will encounter programming questions in interviews that must be solved with recursion. Therefore, this is a necessary concept to learn and practice for a career in software development.
References
Malik, D. S. (2013). C++ Programming: From Problem Analysis to Program Design (6th ed.). Cengage Learning.