Best way to approach recursion in JavaScript?

Question

I have been mostly programming in Python. And this year, I learned how to do recursion using it.

A really good technique my prof taught me is to use list comprehensions like so:

def list_all(obj):  

    if not isinstance(obj, list):  
        return [obj]  
    else:  
        return sum([list_all(x) for x in obj], [])

Now that I am using JS more and more instead of Python, I am wondering what are specific built-in functions you can use in the language to help with recursion. I know that list comprehension are deprecated in JavaScript, so obviously I can't use them anymore. Would map or filter be good substitutes for list comprehensions in tackling recursion? If not, then what?

*"I know that list comprehension are deprecated in JavaScript"* - Who told you that?! When did we ever have list comprehensions and why would they ever be deprecated!? — Andrew Li, Mar 19 '17 at 20:19
@AndrewLi: `[for (x of [1,2,3]) x*x]` - try this in your Firefox console ;) — georg, Mar 19 '17 at 20:24
@georg I understand that future ES versions are implementing list comprehensions but they're not standardized. The problem is the OP claims that they've existed before as a standard and have become deprecated which is not true. — Andrew Li, Mar 19 '17 at 20:25
@AndrewLi: this isn't correct either, comprehensions were there long before 2015, they were planned for the abandoned ES4 (2007). — georg, Mar 19 '17 at 20:36
The "deprecation" statement is wrong. It's more that it is not recommended as it is not *standard* to use per the MDN doc: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Array_comprehensions. That's about it. — idjaw, Mar 19 '17 at 20:37
@georg Ah, I see. I wasn't aware of that. Thanks for the information — Andrew Li, Mar 19 '17 at 20:46
Your prof's "really good technique" is not really good at all: it's a violation of Python's duck-typing principle, and does not handle iterables that are not lists, e.g., strings, tuples or generators. See http://stackoverflow.com/questions/1952464/in-python-how-do-i-determine-if-an-object-is-iterable — Paul Cornelius, Mar 20 '17 at 01:17

georg · Accepted Answer · 2017-03-19T20:39:49.993

Array comprehensions were proposed and implemented by Mozilla as a part of their "Javascript 1.7" initiative (support of then-upcoming and later abandoned ES4) back in 2007, unfortunately they didn't make their way to the current standard (surely, something like Object.getOwnPropertySymbolsOrSomeOtherUnreadableMess() is much more important in terms of redability and efficiency). So, in JS you have to resort to .map for this kind of stuff:

let list_all = obj => {
   if (!Array.isArray(obj))
        return [obj];
    else
        return [].concat(...obj.map(list_all))
}

score 1 · Answer 2 · answered Mar 19 '17 at 20:37

In JavaScript you can indeed use Array prototype methods like .map(), .reduce(), .some(), .every(), .filter(), to get things done, also recursive calls on arrays. In ES6 the spread syntax (much like the * in Python) allows to turn arrays into function arguments. In JavaScript arrays are concatenated with the .concat() method instead of Python's +, and the ternary operator is used more often than the ... if ... else ... operator in Python.

Here is the ES6 code that does what your example Python script does:

function flattenArray(obj) {
    return Array.isArray(obj) 
        ? [].concat(...obj.map(flattenArray)) 
        : [obj];
}
// Sample call:
var res = flattenArray([1,[2,3],[4,[5,6],7],8]);

console.log(res);

score 1 · Answer 3 · edited May 23 '17 at 12:17

Well this is a really broad question, but in general, JavaScript lends itself to some very practical functional solutions. In the code below, I've defined flatten as a very simple recursive procedure that does a simple case analysis on the head of an Array. To me, this reads better than [].concat examples that are provided in other answers - also, there's nothing wrong with Array.prototype.map but I don't think there's any gain in using it here.

const flatten = ([x,...xs]) => {
  if (x === undefined)
    return []
  else if (x.constructor === Array)
    return [...flatten(x), ...flatten(xs)]
  else
    return [x, ...flatten(xs)]
}

let result = flatten([1,[2,3],[4,[5,6],7],8])

console.log(result)
// [ 1, 2, 3, 4, 5, 6, 7, 8 ]

But, if you want a more in-depth answer, I'd look at an answer I posted here:

Merge/flatten an array of arrays in JavaScript

I have a couple other answers about recursion and array operations that might be useful to you

I hope you find these helpful. If you have any questions, let me know.

Best way to approach recursion in JavaScript?

3 Answers3