Process hierarchical data using recursion or stack

README.MD

Process hierarchical data using recursion or stack

This is an example of how to process data in hierarchical structures using either recursion or a stack based approach. To examplify this we will use a didactical example: find the maximum number in an array of arrays. The same techniques can be used to find / process data in other hierarchical structure such as XML documents, JSON objects, etc.

array_recursion_stack.html

<script>

var ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];

console.log( findMax1(ar) );
console.log( findMax2(ar) );


// Use recursion to find the maximum numeric value in an array of arrays
function findMax1(ar)
{
    var max = -Infinity;

    // Cycle through all the elements of the array
    for(var i = 0; i < ar.length; i++)
    {
        var el = ar[i];

        // If an element is of type array then invoke the same function
        // to find out the maximum element of that subarray
        if ( Array.isArray(el) )
        {
            el = findMax1( el );
        }

        if ( el > max )
        {
            max = el;
        }
    }

    return max;
}



// Use a stack to find the maximum numeric value in an array of arrays
function findMax2(arElements)
{
    var max = -Infinity;

    // This is the stack on which will put the first array and then 
    // all the other sub-arrays that we find as we traverse an array     
    var arrays = [];

    arrays.push(arElements);

    // Loop as long as are arrays added to the stack for processing
    while(arrays.length > 0)
    {
        // Extract an array from the stack
        ar = arrays.pop();
        
        // ... and loop through its elements
        for(var i = 0; i < ar.length; i++)
        {
            var el = ar[i];

            // If an element is of type array, we'll add it to stack
            // to be processed later
            if ( Array.isArray(el) )
            {
                arrays.push(el);
                continue;
            }
            
            if ( el > max )
            {
                max = el;
            }
        }
    }

    return max;
}

</script>