title: Python recursive function not returning
body: <p>I am trying to write a recursive function that returns the position of a word in a sorted word list, or return <code>None</code> when the word is not found. The following is the code:</p>
  <pre><code>def partition(t,kw,upper,lower):
      if ((upper-lower) &gt; 1):
          pivot = lower + (upper-lower)//2
          print(&quot;pivot is now {}&quot;.format(pivot))
          if (kw &gt;= t[pivot]):
              lower = pivot
              print(&quot;searching on the right&quot;,upper,lower)
              return(partition(t,kw,upper,lower))
          
          elif (kw &lt;= t[pivot-1]):
              upper = pivot-1
              print(&quot;searching on the left&quot;,upper,lower)
              return(partition(t,kw,upper,lower))
  
          else:
              return None 
              #that means the keyword is between t[pivot-1] and t[pivot]
              #which means it doesnt exist in the list
      if (upper - lower) &lt;= 1:
          if (kw == t[upper]):
              print(&quot;found element {} at upper bound {}&quot;.format(kw,upper))
              return(upper)
          elif (kw == t[lower]):
              print(&quot;found element {} at lower bound {}&quot;.format(kw,lower))
              return(lower)
          else:
              return None
  
  def search(t, kw):
      u = len(t)
      partition(t,kw,u,0)
  </code></pre>
  <p>As you can see I returned the function whenever I called it(not returning is a common mistake in using recursive calls). At the same time, here's the sample array I was using:</p>
  <pre><code>['', '', '150', '150', '1997,with', '36', '49', 'An', 'Annotated', 'Annotation', 'Bibliography', 'China', 'Chinese', 'Chinese', 'Classical', 'During', 'Dynasty', 'Hong', 'Hong', 'Hong', 'Hong', 'Hong', 'In', 'It', 'Kong', 'Kong', 'Kong', 'Kong,', 'Kong.', 'Mainland', 'Poets', 'Qing', 'They', 'Together,', 'Writings', 'a', 'a', 'a', 'a', 'a', 'active', 'activity,', 'addition', 'almost', 'and', 'and', 'and', 'and', 'and', 'and', 'annotations', 'anthologies', 'basic', 'been', 'before.', 'bibliographic', 'bibliographies,', 'by', 'carry', 'ci-poetry', 'ci-poetry', 'classical', 'collected', 'commentaries', 'compilation,', 'compilations', 'compiled', 'covered,', 'development', 'events', 'focused', 'form', 'form', 'formation,', 'from', 'from', 'has', 'help', 'hidden', 'in', 'in', 'in', 'in', 'includes', 'individual', 'information', 'information', 'introduces', 'invaluable', 'is', 'late', 'literary', 'literati', 'literature', 'literature.', 'membership,', 'most', 'never', 'not', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'of', 'offer', 'on', 'on', 'on', 'on', 'order', 'over', 'past', 'periods', 'pioneer', 'pity', 'poetic', 'poetry', 'poetry', 'poetry', 'poet’s', 'political', 'previous', 'previously', 'published', 'refuge', 'research', 'sequel', 'shi-', 'shi-', 'societies', 'societies', 'societies', 'societies.', 'societies.', 'splendor,', 'that', 'that', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'the', 'these', 'these', 'these', 'this', 'times', 'to', 'to', 'to', 'to', 'to', 'to', 'took', 'tools', 'topic', 'tradition.', 'turmoil', 'two', 'uncover', 'understand', 'understanding', 'unique', 'up', 'various', 'very', 'volume,', 'which', 'works,', 'worthwhile', 'would', 'years,']
  </code></pre>
  <p>I was searching for the word <code>&quot;Qing&quot;</code>, it should end up in the 31st position.
  Right now it seems like the function could find the word I need, but couldn't return:</p>
  <pre><code>the result is
  pivot is now 92
  searching on the left 91 0
  pivot is now 45
  searching on the left 44 0
  pivot is now 22
  searching on the right 44 22
  pivot is now 33
  searching on the left 32 22
  pivot is now 27
  searching on the right 32 27
  pivot is now 29
  searching on the right 32 29
  pivot is now 30
  searching on the right 32 30
  pivot is now 31
  searching on the right 32 31
  found element Qing at lower bound 31
  None
  </code></pre>
  <p>I tried searching for issues relating to recursive functions but didn't seem much related content. Most posts on SO are caused by not returning the recursive function, and I am really not sure what's wrong in here.</p>