title: WHILE vs IF when using recursion in Python
body: <p>I am trying to build Quick Sort algorithm in Python. After finding the first pivot index with <code>partition</code> it runs recursively on the left and right side. This is where I get maximum depth recursion error while calling <code>quick_sort</code> function recursively on each side. Dive into the debugging, but still could not pinpoint the issue.</p>
  <p>This is my code:</p>
  <pre><code>def partition(container, start_idx, end_idx):
      pivot_idx = start_idx
      while start_idx &lt; end_idx:
          while start_idx &lt; len(container) and container[start_idx] &lt;= container[pivot_idx]:
  
              start_idx += 1
  
          while container[end_idx] &gt; container[pivot_idx]:
              end_idx -= 1
  
          if start_idx &lt; end_idx:
              container[start_idx], container[end_idx] = container[end_idx], container[start_idx]
  
      container[pivot_idx], container[end_idx] = container[end_idx], container[pivot_idx]
  
      return end_idx
  
  def quick_sort(container, start_idx, end_idx):
      while start_idx &lt; end_idx:
          pivot_index = partition(container, start_idx, end_idx)
          quick_sort(container, start_idx, pivot_index - 1)
          quick_sort(container, pivot_index + 1, end_idx)
  
  container = [6, 5, 4, 8, 9]
  quick_sort(container, 0, len(container) - 1)
  </code></pre>
  <p><strong>UPDATE: I actually pinpointed the issue. Please refer to the answer of mine below.</strong></p>
  <p>The problem is actually about using <code>if vs while</code> when running recursively</p>
  <p>The difference between <code>while and if</code> when running functions recursively is that after reverting back to higher stack levels <code>if</code> does not check the body of stack again or formally speaking, <code>if</code> checks the conditional only once. On the contrary, <code>while</code> checks it again and if the value of variable stays the same at the given higher stack, you end up with infinite recursion at every stack level. Another problem is that it is nearly impossible to detect that feature of <code>while</code><strong>(with recursion)</strong> when debugging, unless you have an eagle eyes.</p>
  <p>This is the simple example:</p>
  <pre><code>def divide_by_half(number):
      while number &gt; 1:
          print(number)
          divide_by_half(number//2)
  
  
  def divide_by_half(number):
      if number &gt; 1:
          print(number)
          divide_by_half(number//2)
  
  divide_by_half(6)
  </code></pre>
  <p>When running with <code>while</code> variable number will stay the same at every higher stack thus causing recursion. If you still want to utilize while, simple fix will be changing variable at that level, outside a function:</p>
  <pre><code>def divide_by_half(number):
      while number &gt; 1:
          number //= 2
          print(number)
          divide_by_half(number)
  </code></pre>
  <p>In that way, you ensure that when you reverted back to higher stack, the variable of interest will change and at some point causing while loop at that level become false.</p>
  <p>Refer to this <a href="https://coderanch.com/t/678313/languages/Recursion-kicks-ass" rel="nofollow noreferrer">forum</a> for further discussion (especially answer given by William Ng)</p>