# Algorithm Time: Recursion Pt. II

## Understanding recursion is a feat in itself, but implementing it is a different story.

This article will follow up last week’s post where I delve into what it meant to think recursively. As a refresher, recursion is a problem solving method that involves a process calling itself within it’s process. In terms of JavaScript, it’s a function that calls itself. If you have a function called `helloWorld()`

you might see is call `helloWorld()`

within it. When writing our functions, we must keep in mind that in order to stop our function from creating an infinite loop and exceeding the call stack, we need a base case. It acts as a way to break the loop if a certain condition is reached. Now that you’re up to speed, let’s see recursion in action.

# The Problem 👀

Write a function calledcollectOddNumberswhich accepts an array of integers and collects all theodd valueswithin the array.collectOddNumbers([1, 2, 3, 4]) // 1, 3

collectOddNumbers([10, 3, 2, 31, 4, 3]) // 3, 31, 3

So what’s this prompt asking us? We’re going to receive some random numbers, but what we want to return are only the values that are odd. Normally we could use an iterative method like using a `for`

loop, to go through the array, but instead we can only rely on our function. We also have to begin to think about what condition can we set so that our function doesn’t infinitely run. A `for`

loop consists of a an initial expression, a condition, and an incremented expression. The condition is used to ensure that the statement only runs based on whether or not it satisfies it (true/false). Instead, that job is going to given to our base case which will be checked at the beginning of our function `collectOddNumbers()`

. Finally, we have to ensure that we actually call our function with a different input value than what was previously given otherwise we’d only be evaluating the same inputs and our base case is never reached.

# Breaking It Down 🎤

If we’re just thinking out loud, our function should go through our collection, perform some sort of logic that checks to see if it’s odd or not, and then place that value somewhere. By the end of our process, we should end up with another collection that only contains odd numbers. Now we come across an interesting problem. If we used iteration instead, we would store our odd collection within an array. Since we are using recursion, every time our function is called, it’s recommended to evaluate one value at a time. We can still use an array to store our odd number, but we can only do so one at a time. Our return statement will have to consider that in our stack, we are going to end up with several little arrays that will need to become one big array.

**function collectOddNumbers(arr) {**

1. Create an array that'll collect our odd number.

2. Establish base case that checks whether or not we have any values left.

a. No more values? Return an empty collection.

3. Logic that checks to see if the number is odd.

a. If it is, push that value into our array.

4. Call our function again.

a. Refine our collection by turning all arrays into one.

b. Remove the current value from our array for the next input.

5. Return our collection that contains **only odd** numbers.

**}**

# Let’s Code! 💻

It is time to put our strategy into action.

We need something that’ll hold the values that are odd. Since our function is recursive, any value we define within our process will get reset so we can remember one value at a time. We’ll make sure we gather all of them up again later so don’t worry.

**1. Create an array that'll collect our odd number.**

let oddNums = [];

Before anything happens, we first have to get through our base case. If we are checking values and constantly decreasing that input, what happens when we have no values left to check? We stop. Our base case should see if we have anything left in our array. If we don’t have anything, we just return an empty array. If we don’t return anything, we will end up with `undefined`

within our collection.

**2. Establish base case that checks whether or not we have any values left.**

a. No more values? Return an empty collection.

if(input.length === 0) {

return oddNums;

}

How exactly do we check if a value is odd? Even values like 2, 4, or 6 all have two thing in common: they can be divided by 2 and have no remainders. We can use this logic to check to see if any values don’t have a remainder of 0.

**3. Logic that checks to see if the number is odd.**

a. If it is, push that value into our array.

if(input[0] % 2 !== 0) {

oddNums.push(input[0])

}

Now here’s a slightly tricky bit. To make our function hit the base case, we are constantly altering the input by separating the current value from the rest of the array by using `slice()`

. That way, the next call will evaluate the next value in the array. With each call, we want to make sure that the following arrays get merged into one by using `concat()`

. Finally we will redefine our collection which would have either held a value or an empty array, with the our new single array. If this confusing to visualize, scroll down to the solution section to see a small tree with what this process might look like! 👇🏼

**4. Call our function again.**

a. Refine our collection by turning all arrays into one.

** b. Remove the current value from our array for the next input.**

oddNums = oddNums.concat(collectOddNumbers(input.slice(1)))

After all our hard work, we want to see that beautiful single array we created so return it!

**5. Return our collection that contains ***only* *odd* numbers.

return oddNums

# Solution With a Side of Stack 🍔

With recursion, I find it easier to visualize with the call stack might look like by creating a small tree and what their return value might look like. By starting with a smaller input, this can also help with seeing how your function might work as the stack increases. I included what it might look like within our solution!

# Final Thoughts 🥛

Each process of recursion is almost like going through a single loop if you were to use iteration. Our base case would act as our condition that we would normally see in loop construction. Now even though in the example we used we only had one “loop” going at a time because we only called our function once with our process, it can get messier. Notice that I mentioned the word *once. *Processes aren’t only restricted to calling themselves once and can call on themselves however many times. With each call, we can begin to construct a tree of values and instead of waiting for a loop to finish, we can have each loop happening simultaneously. I know, crazy right 🤯?