DEV Community

loading...
Cover image for Algorithm Approach: Retrieve Depth

Algorithm Approach: Retrieve Depth

Eric Saldivar
Software Engineer with a passion for working with the development community!
・3 min read

Hey all! This is my first algorithm approach where I utilize RECURSION! Let's hope for the best and dive in! So what is recursion? In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time.-- Epp, Susanna (1995). Discrete Mathematics with Applications.

Alt Text

The simple way I think of recursion is when a function calls itself. Usually functions return a value to be accessed outside of their scope.

So the algorithm:

retrieveDepth([2, [4, [7], 1], 5], 2)
Enter fullscreen mode Exit fullscreen mode

Given an arbitrarily nested array of numbers and a positive integer "depth",return a new array consisting of the numbers with depth less than or equal to the provided depth, in order of appearance.

The original array is considered to be at depth 1, and inner arrays are at
greater depth.

What does it mean? The first parameter will be an array with nested arrays, depths ranging from one level deep to many levels deep. The second argument will be the depth you are required to go into, the depth of the inner arrays.

So how can we visualize this problem?

Alt Text

The first layer of the array means you can access the values and they won't be arrays. The following levels are nested. If you are required to go deeper than the first level you will bring up the values nested into the matching depth that you dive.

The approach:

We need a base case which is the condition when met stops our function and returns an output. Without a base case our function would call itself endlessly and create a stack overflow, when a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack's bounds).

Alt Text

The base case is:

if(depth <= 1) return arr.filter(value => !Array.isArray(value));
Enter fullscreen mode Exit fullscreen mode

When we are at the depth of one, we will no longer dive and return the array but we need to filter through it. We are applying the filter method. We only want values that are not arrays. We iterate through the array and if a value is an array we do not include it in the newly filtered array. We are checking with Array.isArray(value) but we have a ! (bang operator) which when placed in front of a boolean value it will reverse the value, returning the opposite. So we will receive all values that are not arrays.

The recursive call is:

return retrieveDepth(arr.flat(), depth - 1);
Enter fullscreen mode Exit fullscreen mode

We return the function but the arguments are different. We flatten the array with each new call and decrement the depth by 1. We do this until we reach our base case, which is when the depth is less than or equal to 1. Less than to catch any weird arguments that are less than 1 initially and 1 as we decrement we should eventually reach 1.

Just a quick note on what array.flat() does. The flat() method creates a new array with all sub-array elements concatenated into it recursively up to the specified depth.

Our function at a final glance.

const retrieveDepth = (arr, depth) => {
  if(depth <= 1) return arr.filter(value => !Array.isArray(value));
  return retrieveDepth(arr.flat(), depth - 1);
}
Enter fullscreen mode Exit fullscreen mode

We can expect our evaluated result to be:

Alt Text

And that's it! Any questions? Reach out! Thanks for reading and have a great day!

Discussion (0)