Steamroller Algo (recursive solution question)

JavaScript
#1

Tell us what’s happening:
Describe your issue in detail here.

I’ve found recursive to be a bit challenging to conceptualize but I found it necessary to use it in this algorithm after trial and error with nested loops.

The code I have is correct but I don’t understand how this code does not infinitely loop if there is an empty array, or if the last element in the entire array is an empty Array. Like I said it works even with some ugly multi dimensional arrays I’ve tested.

Thanks in advance for your help as I will need it taking on recursion.

  **Your code so far**


function steamrollArray(arr) {
let newArr = [];

function checkArr(arr) {
  for (let ele of arr) {
    if (!Array.isArray(ele)) {
      newArr.push(ele);
    } else checkArr(ele);
  }
}
checkArr(arr);
return newArr;
}

steamrollArray([1, [2], [3, [[4, [[]]]]]]);


  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/90.0.4430.212 Safari/537.36

Challenge: Steamroller

Link to the challenge:

#2

This for loop

for (let ele of arr)

will exit (do nothing) when arr is empty. So if you have an element like [[[]]]
you will recurse three times

[[[]]] --> [[]] --> []

At the end, it’s empty list so it returns doing nothing. Recursion at the level of [[]] completes its for loop and exits. Recursion at the top level also complete its for loop and exits, outputting an empty array.

1 Like
#3

Thanks. I need to look into recursion more but I understand the for loop does nothing if there’s nothing to loop through

#4

Your solution is fine, but speaking generally, IMHO you want to not think about or rely on loop when working on recursive routines. There are cases you need to use loop inside a recursive routine, but to learn recursion and understand it better, you want to practice recursion without using any loop.

To start with a basic example, here’s how you get a sum of an array.

const sum = (arr) => {
  if (arr.length == 0 ){
    return 0
  } else {
   return arr[0] + sum(arr.slice(1))
  }
}

We divide the array into two parts: the non-recursive part arr[0] and the recursive part sum(arr.slice(1)). The recursive thinking is "the sum of an array of length N is the sum of the first element and the sum of the rest of the array.

For the steamrollArray problem, we apply the basic recursive thinking as such

if (arr is empty) {
  return [ ]
} else {
  if (arr[0] is an array) {
     return steamrollArray(arr[0]).concat(rest of arr)
  } else { //first element x is not an array, make it to an array [x] then concat
    return [arr[0]].concat(rest of arr)
  }
}

Translating it in JS, we have

const steamrollArray = (arr) => {
  if (arr.length == 0) {
    return []

  } else {
    if (Array.isArray(arr[0])) {
      return steamrollArray(arr[0]).concat(steamrollArray(arr.slice(1)))
    } else {
      return [arr[0]].concat(steamrollArray(arr.slice(1)))
    }
  }
}

The code gets slightly cleaner (in my opinion), if we use the spread operator

const steamrollArray = (arr) => {
  if (arr.length == 0) {
    return []

  } else {
    const [head, ...rest] = arr
    const top = (Array.isArray(head)) ? steamrollArray(head) : [head]
    return top.concat(steamrollArray(rest))
  }
}

There are other ways to write the function, but the key point I want to illustrate is to use, as much as possible. the basic recursive thinking that does not involve loop when you’re learning/practicing recursion.

3 Likes
#5

+1 to this. This sort of faux-recursion misses the point of recursion and may be masking misunderstandings.

#6

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.