title: How to prevent stack overflow in this recursive path finding algorithm?
body: <p>I have a function that takes two sets of numbers</p>
  <pre><code>([2,2],[6,6]) or ([4,6],[6,12]) etc.
  </code></pre>
  <p>Which represent indexes of elements on a 2D array.
  The function takes the first set, and adds 2 randomly to either of the numbers in the array, until it both numbers are equal to the second set.
  which results in a &quot;pathAB&quot;, we go from first set to the second and push all the elements into an array.</p>
  <p>Then i need to take the second set, and randomly subtract or add 2 to either of the numbers, until they are equal to the first set. I need to find a way back to the starting point [2,2]. The conditions are is that i can't use any of the numbers that are already used in the 'PathAB', or repeat any numbers that where already used while forming the second path. I need to avoid the first path, and &quot;go around it&quot;.</p>
  <p>So for input</p>
  <pre><code>([2,2], [6,6])
  </code></pre>
  <p>the output would be</p>
  <pre><code>  /// First Output
     
    [2, 2], // Point A
    [4, 2],
    [4, 4],
    [6, 4],
    [6, 6], /// Point B
    [4, 6],
    [2, 6],
    [2, 4],
    [2, 2], /// Point A
  </code></pre>
  <p>or it could be</p>
  <pre><code>  /// Second Output 
   
    [2, 2], /// Point A
    [2, 4],
    [4, 4],
    [4, 6],
    [6, 6], /// Point B
    [8, 6],
    [8, 4],
    [6, 4],
    [6, 2],
    [4, 2],
    [2, 2], /// Point A
  </code></pre>
  <p>The whole point is that it should be a Random Path.</p>
  <p>I use this function to build random shapes on a two 2D array. To better understand what i'm trying to do, please have a look at the images linked below.</p>
  <p><a href="https://i.stack.imgur.com/hXYVb.png" rel="nofollow noreferrer">First Output</a>, <a href="https://i.stack.imgur.com/c8xi8.png" rel="nofollow noreferrer">Second Output</a></p>
  <p>The red line is path A to B, or [2,2] to [6,6]. And the green line is path B to A, or [6,6] to [2,2].</p>
  <p>The function i have right now, is able to build a path, 85% of the time
  The other 15% of the time, it gives me a stack overflow error. And the wider the distance between points, the higher the chance of stack overflow. The current function only works well for very small distances.</p>
  <p>Now to the function itself.</p>
  <p>The making of path from A to B, is fairly simple.</p>
  <pre><code>  let pathAB = [];
    let startP;
  
    function makePathAB(a, b, start) {
      if (start) { /// if it's the fist iteration. add the starting point to the PathAB
        pathAB.push(a);
        startP = a;
      }
      if (a[0] === b[0] &amp;&amp; a[1] === b[1]) return; /// A === B, path compelete
      if (a[0] &gt; b[0] || a[1] &gt; b[1]) {
        /// A is beyound boundaries of B, start again
        pathAB = [];
        makePathAB(startP, b, true);
      } else {
        let newA = [...a]; // Take a random index 
        let randomElem = randomInt(0, 1);
        newA[randomElem] += 2; /// go down (+2) in a random direction
        pathAB.push(newA);
        makePathAB(newA, b, false); // start next step
      }
    }
  </code></pre>
  <p>I take the starting point, add 2 to to either of the indexes, and then recuresively call the function until A is equal to B. If a0 or a1 is more than b0 b1 then i scrap the whole path and start again.</p>
  <p>Then i make an array of strings from pathAB, to compare against the steps of the pathBA</p>
  <pre><code>  let compareAB = pathAB.slice(1, pathAB.length - 1).map((item) =&gt; item.toString());
  </code></pre>
  <p>Then for the B to A path i use this function</p>
  <pre><code>  function makePathBA(b, a, start) {
      if (start) {
        /// if starting, push first step of the path to path arr
        pathBA.push(b);
      }
  
      if (a[0] === b[0] &amp;&amp; a[1] === b[1]) return; /// B === A, path, compareABelete
  
      if (b[0] &lt; 0 || b[1] &lt; 0 || b[0] &gt; 8 || b[1] &gt; 8) {
        /// B is out of boundaries of either A, or the array itself
        pathBA = [];
        makePathBA(startPB, a, true);
      } else {
        let newB = [...b];
        let randomElem = randomInt(0, 1);
        let plusminus = [2, -2];
        newB[randomElem] = newB[randomElem] + plusminus[randomInt(0, plusminus.length - 1)]; /// randomly go either up(-2) or down(+2)
  
        let crossed;
  
        pathBA.forEach((item) =&gt; {
          /// Check for path B crossing itself
          if (item.toString() === newB.toString()) {
            crossed = true;
          }
        });
  
        /// THE CAUSE OF THE PROBLEM
        compareAB.forEach((item) =&gt; {
          /// check for path BA crossing path AB
          if (item === newB.toString()) {
            crossed = true;
          }
        });
  
        if (crossed) {
          /// if path BA crossed itself or AB, start again from 0
          pathBA = [];
          makePathBA(startPB, a, true);
          return;
        } else {
          /// else take the next step
          pathBA.push(newB);
          crossed = false;
  
          makePathBA(newB, a, false);
          return;
        }
      }
    }
  </code></pre>
  <p>I take the starting point. Randomly either add or subtract 2 from either of the indexes, and if this step crosses either pathAB or itself, we start again from the starting point. If it doesn't  we go on to the next step.</p>
  <p>THE PROBLEM, lies in the compareAB part of the function. If i don't include comparison against the AB, or &quot;allow pathBA to cross PathAB&quot;, i never get a stack overflow, and the function works fine. But i need the paths not to cross.</p>
  <p>How can this be done? How to prevent stack overflow, and possibly make this function work on much larger distances?</p>
  <p>P.S The fact that the step between indexes is 2, and not 1, is irrelevant. I just need it to be 2, for building rectangular shapes on the provided array.</p>