Trouble with basic Python recursion
<p>I'm having some trouble figuring out why my code is not working, and would appreciate if someone could point out what I'm missing.  It's a basic algorithm problem: given a set of distinct sorted integers, determine whether there is an element such that a[i] = i (a[3] = 3, for example).</p>

<p>I've tried to debug it using print statements, but it's only making one call to FindIndex and not recursing. </p>

<p>Here's the code:</p>

<pre><code>import math

def FindIndex(SetToSearch, beginningIndex, endingIndex):
    """Searches a list of sorted integers to see if there is some a[i] == i

    Keyword Arguments:
    SetToSearch -- a list of disctinct sorted integers 
    beginningIndex -- start point of index to search
    endingIndex -- end point to search """
    # calculate midpoint of set
    midpointIndex = math.ceil((beginningIndex + endingIndex) / 2)
    midpoint = SetToSearch[int(midpointIndex)]
    print "beginningIndex: %s, endingIndex: %s" %(beginningIndex,endingIndex)
    print "midpointIndex: %s, midpoint: %s" % (midpointIndex, midpoint)
    # check whether ending index is greater then beginning index
    if (endingIndex &gt; beginningIndex):
        return "There is no value in this set such that a[i] = i"
    if (endingIndex == beginningIndex):
        if SetToSearch[beginningIndex] == SetToSearch[endingIndex]:
            return "a[%s] is equal to %s" % [beginningIndex, beginningIndex]
    if (midpoint == midpointIndex):
        return "The value at index %d" % midpointIndex
    if (midpoint &gt; midpointIndex):
        print "midpoint &gt; midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, 0, midpointIndex)
    if (midpoint &lt; midpointIndex):
        print "midpoint &lt; midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, midpointIndex + 1, len(SetToSearch) -1)
    else:
        "Something is wrong with your program, because you should never see this!"

sampleSet = [-10, -8, -6, -5, -3, 1, 2, 3, 4, 9 ]
lastIndex = len(sampleSet) - 1

FindIndex(sampleSet,0,lastIndex)
</code></pre>
