Finding unique values in an array with possible nested arrays I'm writing a function that receives an array and returns an object with the count of unique values, pretty much like other questions here or in StackExchange. Except that in my case, this array may contain a nested array, like:

var array = [1, 2, 'a', 'b', [3, 'c', 1], 'd', 2, 'b'];


Here is my code:

function findUniques(array, occurrences) {
    if (!occurrences) {
        occurrences = {};
    }

    //checking if parameter passed is an array
    if (Array.isArray(array)) {
        for (let i = 0; i &lt; array.length; i++) {
            //if item is a nested array, call findUniques again
            if (Array.isArray(array[i])) {
                occurrences = findUniques(array[i], occurrences);
            } else {
                //add to/update count in occurrences object
                occurrences[array[i]] = occurrences[array[i]] + 1 || 1;
            }
        }
    }

    return occurrences;
}


It's returning the following object, as it was supposed to:

{ 
    '1': 2, 
    '2': 2, 
    '3': 1, 
    a: 1, 
    b: 2, 
    c: 1, 
    d: 1 
}


My worry is that I'm using recursion. 

Is it possible to optimize this function? 

(Bear in mind that I must only use vanilla JavaScript)
When we use recursion, we are building an algorithm based on an implicit1 stack, the function call stack. We are pushing and popping elements, essentially every time we recurse down and back up. If we make the stack explicit in our code, we can make the method iterative instead, and skip the recursive calls.

A pseudocode version of the algorithm would look like:

function findOccurences(array):
    ensure array is actually an array

    set occurrences to empty object

    create a stack
    push all elements in array onto the stack
    while the stack is not empty:
        if pop returns an array:
            push all of the elements in the popped array onto the stack
            continue while

        process the popped element

    return occurrences


A nice feature in Javascript arrays is that they have stack semantics2, so we can just use a built in array as our stack. We can actually get a little more clever than that, though. Since we are putting every element from one array into our stack, which is also an array, we could just as effectively clone the original array and use that as our stack3. We can then just translate the pseudocode into Javascript.

function findOccurrences(array) {
    if(!Array.isArray(array)) {
        return {};
    }

    var occurrences = {};

    // JS arrays don't have a native clone method so
    // Array#slice with a start point of 0 creates
    // a copy of our array. If handling in the same
    // order is important, tack a .reverse() at the
    // end.
    var stack = array.slice(0);

    while(stack.length !== 0) {
        var nextElement = stack.pop();
        if(Array.isArray(nextElement)) {
            // We use some fanciness here so we don't have
            // to write out an explicit loop
            [].push.apply(stack, nextElement);
            continue;
        }

        occurrences[nextElement] = occurrences[nextElement] + 1 || 1;
    }

    return occurrences;
}




1 Implicit to our algorithm, explicit to our runtime.

2 Array#push, Array#pop

3 We could just use the original array, but since it is passed by reference, we are going to corrupt the array in the process and that could lead to unwanted side effects.