Python Рекурсия и список

Question

Я учусь о рекурсии в Python и у меня есть этот код:

def search(l,key): 
    """ 
    locates key in list l. if present, returns location as an index; 
    else returns False. 
    PRE: l is a list. 
    POST: l is unchanged; returns i such that l[i] == key; False otherwise. 
    """ 

    if l: # checks if list exists 
     if l[0] == key:  # base case - first index is key 
      return True 

     s = search(l[1:], key)  # recursion 
     if s is not False:   
      return s 

    return False   # returns false if key not found 

Может кто-нибудь объяснить мне, что линия

s = search(l[1:], key) 

делает именно? и что делает l [1:] в списке?

Answer 1

Обычный способ рекурсивно обход списка в функциональных языках программирования является использование функции, которая обращается первый элемент списка (названный car, first, head в зависимости от язык) и другую функцию, которая обращается к остальной части списка (cdr, rest, tail). В Python есть не прямой эквивалент этих функций, но мы можем к этому для того же эффекта, используя slices:

lst[0] # first element of a list 
lst[1:] # rest of the elements in the list, after the first 

Например, рекурсивная функция поиска в Python, который определяет, является ли элемент или нет в списке (предикат, потому что она возвращает True или False) будет выглядеть следующим образом:

def search(lst, key): 
    if not lst:   # base case: list is empty 
     return False 
    elif lst[0] == key: # base case: current element is searched element 
     return True 
    else:    # recursive case: advance to next element in list 
     return search(lst[1:], key) 

в примере выше в виду, что легко адаптировать его для решения исходной задачи - как вернуть индекс элемент в списке (если найден) или False (если не найден):

def search(l, key): 
    if not l: 
     return False 
    elif l[0] == key: 
     return 0 
    else: 
     idx = search(l[1:], key) 
     return 1+idx if idx is not False else False 

Answer 2

Он рекурсивно вызывает функцию search с нарезанными данными от l. l[1:] означает все данные, за исключением элементов, до индекса 1. Например,

data = [1, 2, 3, 4, 5] 
print data[1:]   # [2, 3, 4, 5] 
print data[2:]   # [3, 4, 5] 

Вы можете использовать обозначение нарезки, чтобы получить значения между диапазонами, например

print data[1:4]   # [2, 3, 4] 
print data[2:3]   # [3] 

Вы также можете получить все элементы вплоть до определенного индекса (за исключением элемента в индексе)

print data[:4]   # [1, 2, 3, 4] 
print data[:3]   # [1, 2, 3] 

Иногда вы можете не знать индекс элементов с конца. Таким образом, вы можете использовать отрицательные индексы, как этот

print data[-2:]   # [4, 5] 
print data[1:-2]   # [2, 3] 
print data[:-3]   # [1, 2] 

При использовании отрицательных индексов, последний элемент представлен -1, последний, но один с -2 и так далее. Вы можете прочитать больше об этом нарезания нотации в этом excellent answer.

Answer 3

Прохладный. Вот где рекурсия происходит (как вы отметили), вызывая сама функция при том же key, но подмножество списка l (первый элемент не включен).

В основном, он будет продолжать делать это до тех пор, пока в списке не появится key. Если да, то возвращается True. В противном случае весь список будет удален до тех пор, пока список не будет пустым (все элементы были проверены на равенство с key. В этот момент алгоритм отбрасывает и возвращает False.

Это просто скажет вам, есть ли в списке key, но не по индексу.