Intro:
In JavaScript, recursion is the word used to refer to the method of making a function that calls itself over and over again until a certain condition is met. While recursion isn't the most complicated concept to understand by itself, it can be a useful tool to be used in both simple and complicated programs. Recursion is used to repeatedly check and/or alter the value(s) of a variable, element, array, etc. until the desired value or condition is found and causes the function to end. We will now go into the two main parts of a recursive function, starting with the base case.
Base Case:
The base case of a recursive function is the part of function responsible for ending the function whenever the specified condition is met. After the desired result or condition is found (usually by an if statement), the base case ends a recursive function by activating a return statement. The return statement will always end the function it is in, but it can optionally return a specified value to where the function was called. Now we will look at the recursive case.
Recursive Case:
The recursive case is the opposite of the base case, being the part of the function responsible for recalling that same function whenever the condition(s) of the base case haven't been met yet. The recursive case usually calls the function again using a value gotten from the processes within said function, allowing the function to use the same processes to process the same set of data over and over again until the desired result is achieved. If you know JavaScript well, then recursive functions may look similar to another method: for loops.
Recursion vs For Loops:
Recursive functions are very similar to for loops in operation. Both methods use a form of repetition to achieve a desired result. Loops usually iterate through a list of data (usually an array) to perform a task on each piece of data using the same set of code. Recursive functions usually perform the same tasks on a single set or piece of data over and over again in small increments in order to achieve a desired result. The reason for saying the word "usually" in the last two sentences when referring to the types of data inputted into each method is because you can often use almost any type of data in a for loop or recursive function and get the same desired results if both are set up right. For loops are more efficient (meaning that they are faster and take up less processing power and space) than recursive functions and are usually easier to use and understand. Recursive functions, while more complex and resource intensive than for loops, can be easier to use and/or more effective than a for loop whenever the problem has a structure that is more vulnerable to a recursive approach than an iterative one. Long story short, whether you should use a for loop or a recursive function to solve a problem depends on whether the structure of the data favors an iterative approach or recursive approach. Now let's actually look at an example of recursion and compare it to iteration.
Examples of Recursion and Iteration:
Here is a simple example of a recursive function that calls itself repeatedly in order to constantly console log a shrinking number until said number becomes zero. The function even has an emergency return statement that activates whenever a negative number is given, preventing the function from repeating indefinitely:
const stepperToZero = (x) => {
let result = x;//creates a variable that is a copy of the input
console.log(result);//logs result to console
result--;//reduces result's value by one
if (result == 0){
console.log(result);
return;//if result is zero, then logs result to the console and ends the function
}
if (result < 0){
console.log("Try a non-negative number.")
return;//if result is negative, then logs a custom error message to the console and ends the function
}
return stepperToZero(result);//calls the function again with current result
};
stepperToZero(5);//starts the recursive function with an input of 5
In this next example, I used a simple for loop to perform a function similar to that of the last example in order to demonstrate how similar and interchangeable for loops and recursive functions can be at times:
let input = 5;//creates an input variable and sets it to five
for (let i = input; i >= 0; i--){//creates a loop that counts down to zero from the input variable's number
console.log(i);//console logs the current number each time the code in the loop is ran
}
While this for loop version of the program is much more compact and simpler, it has less functionality due to lacking the ability to be activated with a function call or to spit out an error message and end when given a negative input number. Both of these errors can be easily fixed by putting the for loop into a function at the cost of increasing the size of the program.
While the for loop program seemed to be simpler and more efficient for solving the program than the recursive function was, this was due to the problem being a very simple one with an iterative structure that could be very easily solved using iteration and somewhat easily solved using recursion. Trying to figure out whether iteration or recursion can create the easiest solution to a problem can be a difficult endeavor in itself, with some problems having both recursive and iterative solutions that don't differ much in complexity. My advice to those who have trouble telling the difference between data with iterative structures and data with recursive structures would be to use whatever method you are more comfortable with to solve a problem, and then use the other method if the first one didn't work out so well. If recursive functions are so similar to for loops (as well as being arguably more confusing to make and harder for programs to process), then why should we use recursive functions at all?
What Makes Recursion Unique?:
Despite the similarities between recursion and iteration making them somewhat interchangeable, recursive functions have the ability to break down bigger problems with hierarchical structures in order to more easily solve said problems. Problems with hierarchical/recursive structures are ones that have child data containers within parent data containers, meaning that you must reference each of the inner-most data containers as-well-as their parents in order to access all of the data within each available data container. This kind of problem favors recursion more than iteration, with two for loops being required to get the same result as a single recursive function containing a single for loop. Here is an example of a problem with a hierarchical structure being solved with for loops:
let personList = {
person1: {
name: "Pat",
age: 26,
favNum: 21
},
person2: {
name: "Bob the Wise",
age: 200,
favNum: 1
},
person3: {
name: "Miku",
age: 16,
favNum: 39
},
person4: {
name: "Joel",
age: 37,
favNum: 16
}
}
let objectToLookIn = personList;//creates an variable for the program to look inside of and sets it to the object of personList
let dataToLookFor = 16;//creates an input variable for the program to look for in the object and sets it to sixteen
let checkBox = 0;//creates a variable that is equal to 0 when the desired value hasn't been found in the object yet, but becomes equal to 1 when said value is found
for (let key in objectToLookIn){//creates a loop that goes through each key in the personList object
console.log(key);//console logs the currently selected key in the personList object
for (let key2 in objectToLookIn[key]){//creates a loop that goes through each key in each person sub-object
console.log(key2);//console logs the currently selected key in each person sub-object
if(objectToLookIn[key][key2] === dataToLookFor && checkBox === 0){//checks if the value matches the deisred value and if said value has already been found before
console.log("The value of " + dataToLookFor + " was found under " + key2 + ", under " + key + ", under " + objectToLookIn.constructor.name + ".");//console logs the desired value and its position in the object
checkBox++;//increases the value of checkBox to 1 so that only the first instance of the desired value is console logged
}
}
}
…and an example that solves the same problem using recursion:
let personList = {
person1: {
name: "Pat",
age: 26,
favNum: 21
},
person2: {
name: "Bob the Wise",
age: 200,
favNum: 1
},
person3: {
name: "Miku",
age: 16,
favNum: 39
},
person4: {
name: "Joel",
age: 37,
favNum: 16
}
}
let checkBox = 0;//creates a variable that is equal to 0 when the desired value hasn't been found in the object yet, but becomes equal to 1 when said value is found
const finder = (mainObj, wantedData) => {
for (let key in mainObj){
if(mainObj[key] === wantedData && checkBox === 0){//checks if the value matches the deisred value and if said value has already been found before
console.log("The value of " + wantedData + " was found under " + key + " for the person " + mainObj.name + ".");//console logs the desired value and its position in the object
checkBox = 1;
}
if(mainObj.length === 1){//prevents the program from trying to go through each letter in each string within each object
return;
}
finder(mainObj[key], wantedData);//calls the function from inside the function, causing recursion
}
};
finder(personList, 16);//starts the recursive function with inputs of an object (personList), checkbox (which is set to zero to begin with), and whatever data you desire to find (16)
Using recursion in this case is better because not only does it use a few less characters (trust me, I removed the code comments and checked the rest with a word-counting tool), but it also creates a reusable function that can be used with different parameters. Having malleable parameters means you can use this function with nearly any object and desired data/value that you want!
Conclusion:
Recursive functions are a strange but useful tool for looping through/over some sort of data in order to obtain a desired value, result, or condition. Recursive functions are strange in that while it is simple to understand that recursive functions are just functions that call themselves repeatedly, they are also complicated in that you have to understand how recursively calling a function affects the data that goes through the function each time it calls itself. Recursive functions also serve as an alternative to "for loops" that can exploit recursive structures in data. Just like any other JavaScript method, recursion is just a tool that is useful for solving specific problems when they arise.
Links to Sources Used:
-https://www.freecodecamp.org/news/what-is-recursion-in-javascript/
-https://www.geeksforgeeks.org/how-to-understand-recursion-in-javascript/
-https://www.geeksforgeeks.org/what-is-base-case-in-recursion/
-https://www.geeksforgeeks.org/applications-of-recursion-in-javascript/
-https://betterprogramming.pub/recursion-vs-loops-in-javascript-d588c5b0df31
-https://stackoverflow.com/questions/9386375/efficiency-recursion-vs-loop/9386404#9386404
-https://stackoverflow.com/questions/660337/recursion-vs-loops
-https://www.masaischool.com/blog/how-recursion-works-recursion-vs-iteration/
Top comments (1)
I'm not an expert with recursion, so take what I say with a grain of salt.