jQuery: too much recursion But I need recursion for minesweeper

Question

I am relatively new to javascript. I am trying to code my web version of minesweeper. Here is a recursive function I needed, and it looks to work fine until browser gives this "too much recursion" error. The problem is that i need that recursion. Is there any other way to code minesweeper? Here is the demo: http://altynachar.com/minesweeper/

I can post my php code if needed.

function recursive(id){
                var id = id;
                //Determine what kind of cell this is: Clean, Bomb or Adjasent to bomb
                if($("#"+id).hasClass("adj")== true)
                    var under = "adj";
                if($("#"+id).hasClass("bomb")==true)
                    var under = "bomb";
                if($("#"+id).hasClass("clean")==true)
                    var under = "clean";

                //open up the cell          
                $("#"+id).hide();
                $("#under_"+id).show(); 

                //if it is bomb, open up whole grid and button for restart
                if(under == 'bomb')
                {       
                    $(".cover").hide();
                    $(".under").show();
                    $("body").append("<br /><input type='button' value='restart' onClick='javascript:window.location.reload();' />");
                } else {        

                    //if it is clean cell       
                    if(under == "clean")
                    {
                        //get all the adjasent cell ids
                        var split = id.split('-');
                        var row = parseInt(split[0]);
                        var col = parseInt(split[1]);
                        var adjasent = new Array();
                        adjasent[0] = (row-1)+"-"+ (col+1);
                        adjasent[1] =  row +"-"+(col+1);
                        adjasent[2] = (row+1)+"-"+(col+1);
                        adjasent[3] = (row+1)+"-"+col;
                        adjasent[4] = (row+1)+"-"+(col-1);
                        adjasent[5] =  row+"-"+(col-1);
                        adjasent[6] = (row -1)+"-"+(col-1);
                        adjasent[7] = (row -1)+"-"+col;

                        //loop through adjasent cells
                        for(var i=0; i<adjasent.length; i++)
                        {
                            var split2 = adjasent[i].split('-');
                            var row2 = parseInt(split2[0]);
                            var col2 = parseInt(split2[1]);

                            //check if cell is existent
                            if(row2 > 0 && row2 < 17)
                            {
                                if(col2 > 0 && col2 < 17)
                                {
                                    //perform recursion
                                    var adj = adjasent[i];
                                    recursive(adj);
                                } 
                            }                               
                        }
                    }
                } 
            }           

Answer 1

My guess is that if you have 2 clean cells next to each other your code will get in an infinite recursion.

Each iteration recurses to all adjacent cells. So say cell A and B are next to each other, and both are clean. A will call recurse to B, which will then recurse to A, which recurses to B, and so on.

You can either try to clean up your recursion so that it doesn't look at cells that were already seen, or remove the recursion. You can accomplish the same thing by adding any unseen clean cells to a queue, and just keep popping off the end of the queue until it's empty. That might make it easier to avoid checking the same cell twice too.

---

Also, please don't build up strings just to split them into separate data later. Instead of:

adjasent[0] = (row-1)+"-"+ (col+1);
/* ... */
var split2 = adjasent[i].split('-');
var row2 = parseInt(split2[0]);
var col2 = parseInt(split2[1]);

just do

adjacent[0] = { row: row-1, col: col+1 };
/* ... */
var row2 = adjacent[0].row
var col2 = adjacent[0].col

Answer 2

Your recursion is essentially a depth-first search. The problem is that you do not account for visited cells. In other words, say you have 2 cells, A & B:

A B

When you click on A, it searches for adjacent cells, and comes up with a list containing B. You recurse, and then look for neighbors of B, which is a list containing A, and then you recurse again. This cycle never ends.

You need to mark each cell you visit and return if it has already been visited:

function recursive(id){
    var id = id;

    if( $("#"+id).hasClass('visited') ) {
         return;
    }

    $("#"+id).addClass('visited');

    ...

}

Then you need to remove 'visited' from everything after recursion is complete:

$('div').removeClass('visited');

Answer 3

Keep a running array of cell id's to check, and delete these values from the array as you check them.

        var stack = ["first_id_to_check"];

        function check(id){
            var id = id;
            //Determine what kind of cell this is: Clean, Bomb or Adjasent to bomb
            if($("#"+id).hasClass("adj")== true)
                var under = "adj";
            if($("#"+id).hasClass("bomb")==true)
                var under = "bomb";
            if($("#"+id).hasClass("clean")==true)
                var under = "clean";

            //open up the cell          
            $("#"+id).hide();
            $("#under_"+id).show(); 

            //if it is bomb, open up whole grid and button for restart
            if(under == 'bomb')
            {       
                $(".cover").hide();
                $(".under").show();
                $("body").append("<br /><input type='button' value='restart' onClick='javascript:window.location.reload();' />");
            } else {        

                //if it is clean cell       
                if(under == "clean")
                {
                    //get all the adjasent cell ids
                    var split = id.split('-');
                    var row = parseInt(split[0]);
                    var col = parseInt(split[1]);
                    var adjasent = new Array();
                    adjasent[0] = (row-1)+"-"+ (col+1);
                    adjasent[1] =  row +"-"+(col+1);
                    adjasent[2] = (row+1)+"-"+(col+1);
                    adjasent[3] = (row+1)+"-"+col;
                    adjasent[4] = (row+1)+"-"+(col-1);
                    adjasent[5] =  row+"-"+(col-1);
                    adjasent[6] = (row -1)+"-"+(col-1);
                    adjasent[7] = (row -1)+"-"+col;

                    //loop through adjasent cells
                    for(var i=0; i<adjasent.length; i++)
                    {
                        var split2 = adjasent[i].split('-');
                        var row2 = parseInt(split2[0]);
                        var col2 = parseInt(split2[1]);

                        //check if cell is existent
                        if(row2 > 0 && row2 < 17)
                        {
                            if(col2 > 0 && col2 < 17)
                            {
                                stack.push(adjasent[i]);
                            } 
                        }                               
                    }
                }
            } 
        }

        while(stack[0]!==undefined) {
            check(stack[0]);
            stack.splice(0,1);
        }