Как сделать мой поиск рекурсивным для курса 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 и все еще может выглядеть "рекурсивно"

    # recursion for shorter strings

    l = l//2

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