基本Python递归有问题

Question

我很难弄清楚为什么我的代码不起作用，如果有人能指出我遗漏了什么，我将不胜感激。这是一个基本的算法问题：给定一组不同的排序整数，确定是否有一个元素使得a[i]=i（例如a[3]=3）。你知道吗

我试着用print语句调试它，但它只调用了FindIndex一次，没有递归。你知道吗

代码如下：

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 > 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 > midpointIndex):
        print "midpoint > midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, 0, midpointIndex)
    if (midpoint < midpointIndex):
        print "midpoint < 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)

Answer 1

您可以使用for循环这样做：

def find_index_equal_value(set):
    for i in range(0, len(set)):
        val = set[i]
        if(val == i):
           print "Index matches value."

Answer 2

首先，如果看不到发生了什么，那是因为需要打印返回的字符串：

print FindIndex(sampleSet,0,lastIndex)

现在，如果我运行它，我会得到：

beginningIndex: 0, endingIndex: 9
midpointIndex: 4.0, midpoint: -3
There is no value in this set such that a[i] = i

这意味着if匹配：

# check whether ending index is greater then beginning index
if (endingIndex > beginningIndex):
    return "There is no value in this set such that a[i] = i"

。。。当然了-endingIndex应该总是大于beginningIndex！你知道吗

---

为了将来的参考，你打印了字符串吗？你看到输出线了吗？你不明白为什么要用那个分支？你试过用pdb单步遍历代码吗？你知道吗

Answer 3

问题不是递归。只是第一个条件总是真的：endingIndex总是大于beginningIndex。该条件返回时没有递归，因此函数到此结束。你知道吗