To ease into the concept of recursion, let's start with a loop task.
In the Arrays chapter, we examined the join method,
which combines the elements of an array into a single string. If we have
arr = ['L', 'C', '1', '0', '1'], then arr.join('') returns the string
'LC101'.
We can reproduce this action with either a for or a while loop.
Examine the code samples below:
Use a for loop to iterate through the array and add each entry into the newString variable. |
Use a while loop to add the first element in the array to newString, then remove that element from the array. |
|---|---|
1let arr = ['L', 'C', '1', '0', '1'];
2let newString = '';
3
4for (i = 0; i < arr.length; i++){
5 newString = newString + arr[i];
6}
7
8console.log(newString);
9console.log(arr);
Console Output 'LC101'
['L', 'C', '1', '0', '1']
|
1let arr = ['L', 'C', '1', '0', '1'];
2let newString = '';
3
4while (arr.length > 0){
5 newString += arr[0];
6 arr.shift();
7}
8console.log(newString);
9console.log(arr);
Console Output 'LC101'
[ ]
|
Inside each loop, the code simply adds two strings together---whatever is
stored in newString plus one element from the array. In the for loop,
the element is the next item in the sequence of entries. In the while
loop, the element is always the first entry from whatever remains in the array.
OK, the loops join the array elements together. Now let's see how to
accomplish the same task without a for or while statement.
First, state the problem to solve: Combine the elements from an array into a string.
Second, split the problem into small, identical steps: Looking at the loops
above, the "identical step" is just adding two strings together - newString
and the next entry in the array.
Third, build a function to accomplish the small steps: Let's call the function
combineEntries, and we will set an array as the parameter.
function combineEntries(arrayName){
//TODO: Add code here
}
We want combineEntries to repeat over and over again until the task is
complete.
How do we make this happen without using for or while?
for and while loops end when a particular condition evaluates to false. In the examples above, these conditions are i < arr.length and arr.length > 0, respectively.
With recursion, we do not know how many times combineEntries must be
called. To make sure the code stops at the proper time, we need to identify a
condition that ends the process. This is called the base case, and it
represents the simplest possible task for our function.
if the base case is true, the recursion ends and the task is complete.
if the base case is false, the function calls itself again.
We check for the base case like this:
1function combineEntries(arrayName){
2 if (baseCase is true){
3 //solve last small step
4 //end recursion
5 } else {
6 //call combineEntries again
7 }
8}
For the joining task, the base case occurs when we pass in a one-element
array (e.g. [ 'L' ]). With no other elements to join together, the function
just needs to return 'L'.
Let's update combineEntries to check if the array contains only one item.
1function combineEntries(arrayName){
2 if (arrayName.length <= 1){
3 return arrayName[0];
4 } else {
5 //call combineEntries again
6 }
7}
arrayName.length <= 1 sets up the condition for ending the recursion
process. If it is true, the single entry gets returned, and the function
stops. Otherwise, combineEntries gets called again.
Note
We define our base case as arrayName.length <= 1 rather than
arrayName.length === 1 just in case an empty array [] gets passed to
the function.
What if we accidentally typed arrayName.length === 2 as the condition for
ending the recursion? If so, it evaluates to true for the array
['0', '1'], and the function returns '0'. However, this leaves the
element '1' in the array instead of adding it to the string. By mistyping
the condition, we ended the recursion process too soon.
Similarly, if we used arrayName[0] === 'Rutabaga' as the condition, then
any array that does NOT contain the string 'Rutabaga' would never match the
base case. In situations where the base case cannot be reached, the recursion
process either throws an error, or it continues without end---an infinite loop.
Correctly identifying and checking for the base case is critical to building a working recursive process.
Question
We can use recursion to remove all of the 'i' entries from the array
['One', 'i', 'c', 'X', 'i', 'i', 54].
Consider the code sample below, which declares the removeI function.
1function removeI(arr) {
2 if (baseCase is true){
3 //return final array
4 //end recursion
5 } else {
6 //remove one 'i' entry from array
7 //call removeI function again
8 }
9};
Which TWO of the following work as a base case for the function? Feel free to test the options in the repl.it to check your thinking.
!arr.includes('i')arr.includes('i')arr.indexOf('i')===-1arr.indexOf('i') !== -1Experiment with this repl.it.
Question
The factorial of a number (n!) is the product of a positive, whole number and all the positive integers below it.
For example, four factorial is 4! = 4*3*2*1 = 24, and 5! = 5*4*3*2*1 = 120.
Consider the code sample below, which declares the factorial function.
1function factorial(integer) {
2 if (baseCase is true){
3 //solve last step
4 //end recursion
5 } else {
6 //call factorial function again
7 }
8};
Which of the following should be used as base case for the function?
integer === 1integer < 1integer === 0integer < 0Experiment with this repl.it.