RuntimeError: maximum recursion depth exceeded in Python

Question

#Recursive BinaryChop
def recursiveBinaryChop( value, elementList, min, max ):
    if len( elementList ) == 0:
        return -1
    if max <= min:
        if ( max == min and elementList[min] == value ):
            return min
        else:
            return -1
    else:
        midPointOfList = ( min + max ) / 2

        if elementList[midPointOfList] > value:
            max = --midPointOfList
            return recursiveBinaryChop( value, elementList, min, max )
        elif elementList[midPointOfList] < value:
            min = ++midPointOfList
            return recursiveBinaryChop( value, elementList, min, max )
        else:
            return midPointOfList

#Recursive BinaryChop Test Cases
assert recursiveBinaryChop(3, [], 0, 0) == -1
assert recursiveBinaryChop(3, [1], 0, 0) == -1
assert recursiveBinaryChop(1, [1], 0, 0) == 0
assert recursiveBinaryChop(1, [1, 3, 5], 0, 2) == 0
assert recursiveBinaryChop(3, [1, 3, 5], 0, 2) == 1
assert recursiveBinaryChop(5, [1, 3, 5], 0, 2) == 2
assert recursiveBinaryChop(0, [1, 3, 5], 0, 2) == -1
assert recursiveBinaryChop(2, [1, 3, 5], 0, 2) == -1
assert recursiveBinaryChop(4, [1, 3, 5], 0, 2) == -1
assert recursiveBinaryChop(6, [1, 3, 5], 0, 2) == -1
assert recursiveBinaryChop(1, [1, 3, 5, 7], 0, 3) == 0
assert recursiveBinaryChop(3, [1, 3, 5, 7], 0, 3) == 1
assert recursiveBinaryChop(5, [1, 3, 5, 7], 0, 3) == 2
assert recursiveBinaryChop(7, [1, 3, 5, 7], 0, 3) == 3
assert recursiveBinaryChop(0, [1, 3, 5, 7], 0, 3) == -1
assert recursiveBinaryChop(2, [1, 3, 5, 7], 0, 3) == -1
assert recursiveBinaryChop(4, [1, 3, 5, 7], 0, 3) == -1
assert recursiveBinaryChop(6, [1, 3, 5, 7], 0, 3) == -1
assert recursiveBinaryChop(8, [1, 3, 5, 7], 0, 3) == -1

我收到这个简单代码的运行时间错误，我尝试搜索但所有答案似乎都建议设置递归限制，但我没有看到我的测试输入发生这种情况。我不确定我的算法是错误的还是有一些逻辑错误。我在 C++.

中使用相同的算法

请帮忙。

Answer 1

    if elementList[midPointOfList] > value:
        max = --midPointOfList
        return recursiveBinaryChop( value, elementList, min, max )
    elif elementList[midPointOfList] < value:
        min = ++midPointOfList
        return recursiveBinaryChop( value, elementList, min, max )

Python 没有 -- 或 ++ 运算符。如果您尝试递减和递增，请尝试“-1”和“+1”。

    if elementList[midPointOfList] > value:
        max = midPointOfList - 1
        return recursiveBinaryChop( value, elementList, min, max )
    elif elementList[midPointOfList] < value:
        min = midPointOfList + 1
        return recursiveBinaryChop( value, elementList, min, max )

（这与 C++ 的 -- 和 ++ 的行为不完全相同，因为 midPointOfList 的值保持不变，但这似乎并不重要特殊情况；midPointOfList 无论如何都不会在这些行之后被引用）

Answer 2

这两行不是你想的那样：

max = --midPointOfList
min = ++midPointOfList

Python 没有这种自增运算符，但它们确实解析并成功执行。

++i 解析为 +(+i)，--i 解析为 -(-i)。两者都保持 i 不变，实际上是

max = midPointOfList
min = midPointOfList

RuntimeError: maximum recursion depth exceeded in Python

RuntimeError: maximum recursion depth exceeded in Python

python

recursion

binary-search