A recursion example in javascript.

Printing menu items using recursion

<script>
/* 
 * the problem: we have a random list of menu items with multiple level of heirarchy.
 * we want the items to be printed into the desired order
*/

/* ordered properly just for understanding, this array is shuffled and made random before using */
var items = [
    {id: 1,     parent: 0,  order: 2,   title: 'Main Course'},
        {id: 4,     parent: 1,  order: 3,   title: 'Mughlai'},
        {id: 5,     parent: 1,  order: 1,   title: 'Chinese'},
        {id: 6,     parent: 1,  order: 2,   title: 'Italian'},
            {id: 16,    parent: 6,  order: 3, title: 'Italian 3'},
            {id: 17,    parent: 6,  order: 2, title: 'Italian 2 (Pasta)'},
                {id: 19,    parent: 17,     order: 1,   title: 'Pasta 1'},
                {id: 20,    parent: 17,     order: 2,   title: 'Pasta 2'},

            {id: 18,    parent: 6,  order: 1, title: 'Italian 1'},

        {id: 77,     parent: 1,  order: 4,   title: 'Punjabi'},
            {id: 21,    parent: 77,  order: 1,   title: 'Tandoori'},
                {id: 27,    parent: 21,     order: 1,   title: 'Tandoori 1'},
                {id: 26,    parent: 21,     order: 2,   title: 'Tandoori 1'},

            {id: 22,    parent: 77,  order: 2,   title: 'Naan'},
            {id: 23,    parent: 77,  order: 3,   title: 'Tawa'},
                {id: 24,    parent: 23,     order: 2,   title: 'Tawa2'},
                {id: 25,    parent: 23,     order: 1,   title: 'Tawa1'},

    {id: 2,     parent: 0,  order: 1,   title: 'Apetizers'},
        {id: 7,     parent: 2,  order: 1,    title: 'apetizer1'},
        {id: 8,     parent: 2,  order: 2,    title: 'apetizer2'},
        {id: 9,     parent: 2,  order: 3,    title: 'apetizer3'},

    {id: 3,     parent: 0,  order: 3,   title: 'Desserts'},
        {id: 11,    parent: 3,  order: 2,    title: 'Pudding'},
            {id: 14,    parent: 11,  order: 2,    title: 'Pudding 2'},
            {id: 15,    parent: 11,  order: 1,    title: 'Pudding 1'},
                    
        {id: 10,    parent: 3,  order: 1,    title: 'Icecreams'},
            {id: 12,    parent: 10,  order: 1,    title: 'Icecream 1'},
            {id: 13,    parent: 10,  order: 2,    title: 'Icecream 2'},
];

/* desired output 
Apetizers
    - apetizer1
    - apetizer2
    - apetizer3
Main Course
    - Chinese
    - Italian
        - Italian 1
        - Italian 2 (Pasta)
            - Pasta 1
            - Pasta 2
        - Italian 3
    - Mughlai
    - Punjabi
        - Tandoori
            - Tandoori 1
            - Tandoori 2
        - Naan
        - Tawa
            - Tawa1
            - Tawa2
Desserts
    - Icecreams
        - Icecream 1
        - Icecream 2
    - Pudding
        - Pudding 1
        - Pudding 2


*/

/**
 * Randomize array element order in-place.
 * Using Fisher-Yates shuffle algorithm.
 * http://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array#answer-12646864
 */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    return array;
}

function printItems(){
    for( var i=0; i<items.length; i++ ){
        var depth = getDepth(items[i]);
        var spacer = '';

        while( depth>0 ){
            spacer +='&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;';
            depth--;
        }

        spacer += '- ';
        document.write( spacer+items[i].title+'<br/>' );
    }

    document.write('<br/>-------------------------------------------<br/>');
}

function getDepth( item ){
    if( item.parent==0 ){
        return 0;
    }
    else{
        var parent = {parent:0};
        for (var i = newitems.length - 1; i >= 0; i--) {
            if( newitems[i].id==item.parent ){
                parent = newitems[i];
                break;
            }
        };
        return 1+getDepth( parent );//RECURSION
    }
}

function reArrange(){
    if( parents_stack.length==0 || newitems.length==items.length )
        return false;
    
    var parent = parents_stack[0];

    var children = [];
    //find all the elements whose 'parent' is the given argument
        for (var i = items.length - 1; i >= 0; i--) {
            if( items[i].parent==parent ){
                children.push(items[i]);
                //also push it to the parents_stack, so that subsequent calls to this recursive function will check for their children
                parents_stack.push( items[i].id );
            }
        };

    //reorder them based on their 'order' attrubute
        //bubble sort!
        var sorted = false;
        do{
            var switched = false;
            for (var i =0; i< children.length; i++) {
                if( i==0 ) continue;
                var previous_index = i-1;
                var current = children[i].order;
                var previous = children[previous_index].order;
                
                if( current < previous ){
                    //switch them
                    var temp_prev = children[previous_index];
                    children[previous_index] = children[i];
                    children[i] = temp_prev;
                    switched = true;
                }
            }
            //if any switch was made, we will mark sorted as false and will loop one more time
            if( switched === true ){ sorted = false; }
            else{ sorted = true; }

        } while( sorted == false );
    
    
    //insert all of them right after their parent
        //find the position of their parent
            var parent_index = -1;
            for (var i = 0; i < newitems.length; i++) {
                if( newitems[i].id==parent ){
                    parent_index = i;
                    break;
                }
            };
        //insert them after parent
            var child_index = parent_index + 1;//increase by 1
            for (var i = 0; i < children.length; i++) {
                newitems.splice( child_index, 0, children[i] );
                child_index++;
            }

    //finally remove the current parent from parents_stack and call the function again
        parents_stack.splice(0, 1);
        reArrange();//RECURSION
}

//randomise the items array
items = shuffleArray( items );

var newitems = [];
var parents_stack = [0];

//rearrange/properly arrange the items 
reArrange();

//properly arranged items
items = newitems;

//reset parents_stack and print the menu items
parents_stack = [0];
printItems();
</script>