title: Recursion and Dijkstra's Algorithm
body: <p>My recursive algorithm to navigate a maze takes way too long. Any suggestions on how to speed it up to be more efficient? Right now, it goes through every possible solution. When I tried to cut that down, it would then skip over many of the solutions, including the shortest. How do I cut down the number of solutions, or end some solutions early, while not skipping the shortest?</p>
  
  <pre><code> private static void turnsforshortestmove(Vector2 location, int[,] board, int endrow, ref Boolean done, ref int[,] BOARDCHANGE, ref HashSet&lt;int&gt; h)
   //location is current location. board is the maze, endrow is the end y value to get to. it doesn't matter which x value, but as long as they get to the y value it's considered finishing.
   // done is a mistake, ignore it. BOARDCHANGE stores 
  {
      //i need to compare all results for shortest
      //i need to cut off those that cant move
      if (location.Y == endrow)
      {
          h.Add(parseInt(board)); //counts how long the path is
          for (int r = 0; r &lt; 19; r++)
              for (int c = 0; c &lt; 19; c++)
                  BOARDCHANGE[r, c] = board[r, c]; //sets the "real" board to have the path shown
      }
      else
      {
  
          int[,] boardCopy = new int[19, 19];
          for (int r = 0; r &lt; 19; r++)
              for (int c = 0; c &lt; 19; c++)
                  boardCopy[r, c] = board[r, c];
  
          boardCopy[(int)location.X, (int)location.Y] = 8;
  
  
   //this part is saying if the square above isnt a wall, and two squares above isn't occupied, then do this function again
  
          if (boardCopy[(int)location.X, (int)location.Y - 1] == 1)
          {
              if (boardCopy[(int)location.X, (int)location.Y - 2] == 0)
              {
                  turnsforshortestmove(new Vector2(location.X, location.Y - 2), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
              }
          }    
          if (boardCopy[(int)location.X - 1, (int)location.Y] == 1)
          {
              if (boardCopy[(int)location.X - 2, (int)location.Y] == 0)
              {
                  turnsforshortestmove(new Vector2(location.X - 2, location.Y), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
              }
          }
          if (boardCopy[(int)location.X + 1, (int)location.Y] == 1)
          {
              if (boardCopy[(int)location.X + 2, (int)location.Y] == 0)
              {
                  turnsforshortestmove(new Vector2(location.X + 2, location.Y), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
              }
          }
          if (boardCopy[(int)location.X, (int)location.Y + 1] == 1)
          {
              if (boardCopy[(int)location.X, (int)location.Y + 2] == 0)
              {
                  turnsforshortestmove(new Vector2(location.X, location.Y + 2), boardCopy, endrow, ref done, ref BOARDCHANGE, ref h);
              }
          }
      }
  }
  </code></pre>
  
  <p>At the end, it looks through the Hashset to find the shortest path (number).</p>