# 11.7. Recursion Walkthrough: The Base Case¶

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.

## 11.7.1. Joining Array Elements With a 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.

 ```1 2 3 4 5 6 7 8 9``` ```let arr = ['L', 'C', '1', '0', '1']; let newString = ''; for (i = 0; i < arr.length; i++){ newString = newString + arr[i]; } console.log(newString); console.log(arr); ```

Console Output

```'LC101'
['L', 'C', '1', '0', '1']
```
 ```1 2 3 4 5 6 7 8 9``` ```let arr = ['L', 'C', '1', '0', '1']; let newString = ''; while (arr.length > 0){ newString += arr; arr.shift(); } console.log(newString); console.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.

## 11.7.2. Bring In Recursion Concepts¶

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){
}
```

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`?

## 11.7.3. Identifying the Base Case¶

`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:

 ```1 2 3 4 5 6 7 8``` ```function combineEntries(arrayName){ if (baseCase is true){ //solve last small step //end recursion } else { //call combineEntries again } } ```

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.

 ```1 2 3 4 5 6 7``` ```function combineEntries(arrayName){ if (arrayName.length <= 1){ return arrayName; } else { //call combineEntries again } } ```

`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.

## 11.7.4. The Case for the Base¶

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 === '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.

 ```1 2 3 4 5 6 7 8 9``` ```function removeI(arr) { if (baseCase is true){ //return final array //end recursion } else { //remove one 'i' entry from array //call removeI function again } }; ```

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.

1. `!arr.includes('i')`

2. `arr.includes('i')`

3. `arr.indexOf('i')===-1`

4. `arr.indexOf('i') !== -1`

Experiment 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.

 ```1 2 3 4 5 6 7 8``` ```function factorial(integer) { if (baseCase is true){ //solve last step //end recursion } else { //call factorial function again } }; ```

Which of the following should be used as base case for the function?

1. `integer === 1`

2. `integer < 1`

3. `integer === 0`

4. `integer < 0`

Experiment with this repl.it.