Is recursion "fair game" for the intermediate scripting challenges

1

Hi all,

I have what is maybe a strange question. I just finished the “Steamroller” scripting challenge (I’ve been skipping around a lot, doing things that seemed fun). Anyway, it seems to me that the easiest and most efficient way to do this problem is with recursion, but I don’t think that’s been formally discussed in the FCC materials. So, I thought maybe I should find a way to do it without–which I did manage eventually, but it was a bit clunky.

Any thoughts about this?

Thanks!

–RK

3

Steamroller is definitely more intuitive with recursion (if you can wrap your head around recursion). I think Smallest Common Multiple is too. I’ve gone through some of my solutions to provide both a recursive and imperative answer because for a while campers were kind of obsessed with recursion and insisted on seeing a recursive approach to everything.

Use whatever solution seems most appropriate.

1 Like
4

Thanks for the replies, this is helpful!

Perhaps a better way to phrase my question would be: is there a “nice” way to do this without recursion, which I’m not seeing?

Here is a very rough outline of my current non-recursive solution:

  • Create an empty array, called "answer."
  • Loop through my input array (saved as "arr"). If an entry of "arr" is not itself an array, just push that entry onto the end of "answer"; if it's an array, concatenate that array onto the end of "answer" instead. So "answer" is the result of getting rid of the first level of nesting in "arr."
  • Check to see if my new array ("answer") is still nested. If not, return it! If so, repeat the above process, setting "arr" equal to "answer" and "answer" again to an empty array

This works, but I’m not too happy with it. Scanning the array to see if it’s still nested feels really inefficient, and so does creating a new blank array and copying over non-array values at each step. Am I making this all much more complicated than it needs to be?

5

If you already use recursion, why not go all in? :wink: Instead of concatenating arrays you find you could recurse and provide the array you have found as argument. You can use a closure to do that properly:

// semi pseudocode
function steamrollArray(arr) {
  var ans = [];
  function inner(xs) {
    for all x in xs {
      if x is an array: inner(x)
      else add x to answer
    }
  }
  inner(arr);
  return ans;
}

Recursion is great, but there are things one should be aware of.
Every time you enter a function, the location you came from is pushed to the call stack so that the program can return there when the function returns. If you recurse too much (hundreds or thousands of times maybe, I am not sure these days), the call stack runs out of space. A way around that is tail recursion, which is a feature of es6. However, there is currently no browser where its implemented afaik. So tl;dr you should know when recursion is okay to use and when its (currently) better to use a more imperative approach (loops).
For flattening arrays that are like a dozen levels deep, that shouldn’t be a problem at all.

1 Like
6

I’ll echo pretty much the same sentiment, recursion is a tool, know when to use it and when to not, if it fits your problem, then go for it, otherwise, find something thats more in line with what problem your trying to solve.

As far as whether it’s ‘fair game’, in my opinion, pretty much everything is fair game except for the ‘google problem, click stack overflow, copy accepted answer as my own, paste into FCC challenge and hit submit’, that’s plagiarism, and offers absolutely nothing in terms of learning and progression. Everything else should be good.

Happy Coding

1 Like
7

Thanks so much for providing more background about recursion, and when it gets hairy. Very cool!