Python-재귀

재귀를 사용하면 함수가 자신을 호출 할 수 있습니다. 새 값에 대해 고정 된 코드 단계가 반복해서 실행됩니다. 또한 재귀 호출이 종료되는시기를 결정하기위한 기준을 설정해야합니다. 아래 예에서는 이진 검색에 대한 재귀 적 접근 방식을 볼 수 있습니다. 정렬 된 목록을 가져 와서 재귀 함수에 대한 입력으로 인덱스 범위를 제공합니다.

재귀를 사용한 이진 검색

아래 그림과 같이 파이썬을 사용하여 바이너리 검색 알고리즘을 구현합니다. 정렬 된 항목 목록을 사용하고 시작 및 끝 인덱스와 함께 목록을 입력으로 가져 오는 재귀 함수를 설계합니다. 그런 다음 이진 검색 기능은 검색된 항목을 찾거나 목록에없는 것으로 결론을 내릴 때까지 자신을 호출합니다.

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

2
None