如何使我的 MIT 6001x 课程递归搜索

Question

使用 Python 编程，我的任务是递归编写搜索算法，该算法可以在任何给定字符串中找到任何给定字母。然而，即使我的代码在没有任何迭代的情况下完成了工作，评分者仍然抱怨它不是递归的。我怎样才能使它更具递归性以达到相同的目的？

这是我的代码：

def isIn(char, aStr):
    '''
    char: a single character
    aStr: an alphabetized string
    returns: True if char is in aStr; False otherwise
    '''
    l = len(astr)//2
    if astr[l] != astr[0]:
        if astr[l] > char:
            astr = astr[:l]        
        else:
            astr = astr[l:]
    else:
        if astr[l] == char:
            return True
        else:
            return False
    return isin(char, astr)

Answer 1

递归有两个元素：

首先检查它是否有特殊追逐，例如空字符串或长度为 1 的字符串（停止条件）
下一个运行使用较短字符串的相同函数

代码：

def isIn(char, aStr):
    '''
    char: a single character
    aStr: an alphabetized string
    returns: True if char is in aStr; False otherwise
    '''
    l = len(aStr)

    # special cases - stop condition

    if l == 0:
        return False

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

    # recursion for shorter strings

    l = l//2

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

测试：

print( isIn('c', '') ,   isIn('c', '') == False)

print( isIn('c', 'a'),   isIn('c', 'a') == False )
print( isIn('c', 'e'),   isIn('c', 'e') == False )
print( isIn('c', 'c'),   isIn('c', 'c') == True )

print( isIn('c', 'ab'),  isIn('c', 'ab') == False )
print( isIn('c', 'de'),  isIn('c', 'de') == False )

print( isIn('c', 'abc'), isIn('c', 'abc') == True )
print( isIn('c', 'cde'), isIn('c', 'cde') == True )

编辑： 特殊情况你也可以写得更短

def isIn(char, aStr):
    '''
    char: a single character
    aStr: an alphabetized string
    returns: True if char is in aStr; False otherwise
    '''
    l = len(aStr)

    # special cases - stop condition

    if l < 2:
        return char == aStr

    # recursion for shorter strings

    l = l//2

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

编辑： 正如@Dan 在评论中提到的，它可以更有效 - log(n) - 使用 if/else 而不是 or 它可以还是看"recursive"

    # recursion for shorter strings

    l = l//2

    if char < aStr[l]
        return isIn(char, aStr[:l])
    else:
        return isIn(char, aStr[l:])

如何使我的 MIT 6001x 课程递归搜索

How to make my search recursive for MIT 6001x course

python

algorithm

edx