title: Quicksort and tail recursive optimization
body: <p>In <a href="https://rads.stackoverflow.com/amzn/click/com/0262033844" rel="noreferrer" rel="nofollow noreferrer">Introduction to Algorithms</a> <code>p169</code> it talks about using tail recursion for <code>Quicksort</code>.</p>
  
  <p>The original Quicksort algorithm earlier in the chapter is (in pseudo-code)</p>
  
  <pre><code>Quicksort(A, p, r)
  {
   if (p &lt; r)
   {
    q: &lt;- Partition(A, p, r)
    Quicksort(A, p, q)
    Quicksort(A, q+1, r)
   }
  }
  </code></pre>
  
  <p>The optimized version using tail recursion is as follows</p>
  
  <pre><code>Quicksort(A, p, r)
  {
   while (p &lt; r)
   {
    q: &lt;- Partition(A, p, r)
    Quicksort(A, p, q)
    p: &lt;- q+1
   }
  }
  </code></pre>
  
  <p>Where <code>Partition</code> sorts the array according to a pivot.</p>
  
  <p>The difference is that the second algorithm only calls <code>Quicksort</code> once to sort the LHS.</p>
  
  <p><strong>Can someone explain to me why the 1st algorithm could cause a stack overflow, whereas the second wouldn't?</strong> Or am I misunderstanding the book. </p>