Algorithm Time: Recursion Pt. II

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

Daniela Sandoval
Nov 26 · 6 min read
Like Ant-Man, our function’s call stack eventually starts to look like a tree 🧐.

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.

Never forget about your base case!

The Problem 👀

Write a function called collectOddNumbers which accepts an array of integers and collects all the odd values within 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 🎤

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! 💻

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 🍔

Final Thoughts 🥛

Looking at you fibonacci sequence algorithm.

JavaScript in Plain English

Learn the web's most important programming language.

Daniela Sandoval

Written by

Software Developer | Flatiron Alumni | Proud cat mom! 🐈 💻 ✨

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade