为什么递归函数会给我一个错误输出？

Question

我目前正在做edX课程的计算机科学和递归练习之一，我被困在这个问题。我已经在“纸上”检查了几次代码，但看不出有什么问题。你知道吗

问题总结如下： 使用对分搜索方法找出字符串（aStr）中是否存在isIn（char，aStr）函数中的char

下面是我写的代码：

def isIn(char,aStr):

    aStrSorted = sorted(aStr)

    if len(aStrSorted)==0:
        print('The string you have given to me is empty')

    if len(aStrSorted)==1:
        print('The character you are looking for is in the ' + str(aStrSorted))

    if char == aStrSorted[len(aStrSorted) // 2]:
        print('The character you are looking for is in the string ' + str(aStrSorted))

    elif char<aStrSorted[len(aStrSorted) // 2]:
        return isIn(char,aStrSorted[0:len(aStrSorted)//2])
    elif char>aStrSorted[len(aStrSorted) // 2]:
        return isIn(char, aStrSorted[len(aStrSorted) // 2:-1])
    else:
        print('The character you are looking for is not in the string ' + str(aStrSorted))


isIn('f', 'abcdegghkl')

错误消息是：

Traceback (most recent call last):
The string you have given to me is empty
  File "C:/Users/abkk1l/PycharmProjects/edX/edX-2.py", line 29, in <module>
    isIn('f', 'abcdegghkl')
  File "C:/Users/abkk1l/PycharmProjects/edX/edX-2.py", line 22, in isIn
    return isIn(char,aStrSorted[0:len(aStrSorted)//2])
  File "C:/Users/abkk1l/PycharmProjects/edX/edX-2.py", line 24, in isIn
    return isIn(char, aStrSorted[len(aStrSorted) // 2:-1])
  File "C:/Users/abkk1l/PycharmProjects/edX/edX-2.py", line 24, in isIn
    return isIn(char, aStrSorted[len(aStrSorted) // 2:-1])
  File "C:/Users/abkk1l/PycharmProjects/edX/edX-2.py", line 18, in isIn
    if char == aStrSorted[len(aStrSorted) // 2]:
IndexError: list index out of range

Answer 1

考虑到isIn()是一个谓词函数名（应该返回True或False），对字符串进行排序（不必要的是，所有排序的字符串的子字符串）似乎有些过分，我猜您误解了问题，并建议了一个更简单的解决方案，如：

def isIn(char, aStr):

    length = len(aStr)

    if length == 0:
        return False

    if length == 1:
        return aStr[0] == char

    halfway = length // 2

    return isIn(char, aStr[:halfway]) or isIn(char, aStr[halfway:])


if isIn('f', 'abcdefghkl'):
    print('The character you are looking for is in the string')
else:
    print('The character you are looking for is not in the string')