파이썬 재귀 및 목록

Question

나는 파이썬에서 재귀에 대해 배우고 나는이 코드를 가지고 :

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

에 반복적으로 함수형 프로그래밍 언어의 목록을 통과하는 일반적인 방법을이 슬라이스 표기법에 대한 자세한 내용을 읽기 수 언어) 및 목록의 나머지 부분에 액세스하는 다른 함수 (cdr, rest, tail)가 있습니다. 파이썬 이들 기능에 직접 해당되지 않지만, 우리는 같은 효과 이로 slices를 사용하여 수 예

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

, 요소가 있는지 여부를 판정 파이썬 재귀 검색 기능 (이 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

l의 슬라이스 된 데이터로 재귀 호출 search을 호출합니다. 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와 하나입니다. 당신은 head가에 따라 first, car라는 이름의 목록 (의 첫 번째 요소에 액세스하는 기능을 사용하려면이 excellent answer.

Answer 3

차갑다. 이것은 재귀가 발생하는 곳입니다 (언급 한대로), 같은 key을 가진 함수 자체를 호출하지만 목록의 하위 집합 l (첫 번째 요소는 포함되지 않음)을 호출합니다.

기본적으로 목록에서 key이 발견 될 때까지 계속됩니다. 그렇다면 True이 반환됩니다. 그렇지 않으면 목록이 비어있을 때까지 전체 목록이 사라지고 모든 요소는 key과 같은지 확인됩니다.이 시점에서 알고리즘은 포기하고 False을 반환합니다.

key이 목록에 있지만 어떤 색인을 찾을 수 있는지 알려주지 않습니다.