title: Difficulties in converting an recursive algorithm into an iterative one
body: <p>I've been trying to implement a recursive backtracking maze generation algorithm in javascript. These were done after reading a great series of posts on the topic <a href="http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking" rel="nofollow">here</a></p>
  
  <p>While the recursive version of the algorithm was a no brainer, the <a href="https://gist.github.com/754545" rel="nofollow">iterative equivalent</a> has got me stumped. </p>
  
  <p>I thought I understood the concept, but my implementation clearly produces incorrect results. I've been trying to pin down a bug that might be causing it, but I am beginning to believe that my problems are being caused by a failure in logic, but of course I am not seeing where. </p>
  
  <p>My understanding of the iterative algorithm is as follows:</p>
  
  <ul>
  <li><p>A stack is created holding representations of cell states. </p></li>
  <li><p>Each representation holds the coordinates of that particular cell, and a list of directions to access adjacent cells.</p></li>
  <li><p>While the stack isn't empty iterate through the directions on the top of the stack, testing adjacent cells.</p></li>
  <li><p>If a valid cell is found place it at the top of the stack and continue with that cell.</p></li>
  </ul>
  
  <p>Here is my recursive implementation ( note: keydown to step forward ): <a href="http://jsbin.com/urilan/14" rel="nofollow">http://jsbin.com/urilan/14</a></p>
  
  <p>And here is my iterative implementation ( once again, keydown to step forward ): <a href="http://jsbin.com/eyosij/2" rel="nofollow">http://jsbin.com/eyosij/2</a></p>
  
  <p>Thanks for the help. </p>
  
  <p>edit: I apologize if my question wasn't clear. I will try to further explain my problem.</p>
  
  <p>When running the iterative solution various unexpected behaviors occur. First and foremost, the algorithm doesn't exhaust all available options before backtracking. Rather, it appears to be selecting cells at a random when there is one valid cell left. Overall however, the movement doesn't appear to be random. </p>
  
  <pre><code>var dirs = [ 'N', 'W', 'E', 'S' ];
  var XD = { 'N': 0, 'S':0, 'E':1, 'W':-1 };
  var YD = { 'N':-1, 'S':1, 'E':0, 'W': 0 };
  
  
  function genMaze(){
  
  var dirtemp = dirs.slice().slice();    //copies 'dirs' so its not overwritten or altered
  var path = [];                         // stores path traveled.
  
  var stack = [[0,0, shuffle(dirtemp)]]; //Stack of instances. Each subarray in 'stacks' represents a cell
                                         //and its current state. That is, its coordinates, and which adjacent cells have been
                                         //checked. Each time it checks an adjacent cell a direction value is popped from 
                                         //from the list
  
  while ( stack.length &gt; 0 ) {
  
    var current = stack[stack.length-1]; // With each iteration focus is to be placed on the newest cell.
  
    var x = current[0], y = current[1], d = current[2];
    var sLen = stack.length;             // For testing whether there is a newer cell in the stack than the current.
    path.push([x,y]);                    // Store current coordinates in the path
  
    while ( d.length &gt; 0 ) {
      if( stack.length != sLen ){ break;}// If there is a newer cell in stack, break and then continue with that cell
  
      else {
        var cd = d.pop();
        var nx = x + XD[ cd ];
        var ny = y + YD[ cd ];
  
        if ( nx &gt;= 0 &amp;&amp; ny &gt;= 0  &amp;&amp; nx &lt; w &amp;&amp; ny &lt; h &amp;&amp; !cells[nx][ny] ){
  
          dtemp = dirs.slice().slice();
          cells[nx][ny] = 1;
          stack.push( [ nx, ny, shuffle(dtemp) ] ); //add new cell to the stack with new list of directions.
                                                    // from here the code should break from the loop and start again with this latest addition being considered.
  
  
        }
      }
  
    }
  
    if (current[2].length === 0){stack.pop(); } //if all available directions have been tested, remove from stack
  
  
  }
  return path;
  }
  </code></pre>
  
  <p>I hope that helps clear up the question for you. If it is still missing any substance please let me know. </p>
  
  <p>Thanks again.</p>