순환의 개념과 기본 예제 3

순환 함수의 기본 조건

적어도 하나의 base case, 순환되지 않고 종료되는 case가 있어야 함.

모든 case는 base case로 수렴해야 함.

암시적 매개변수가 아닌 명시적 매개변수를 사용해야 함

def search(data,n,target):
    for i in range(n):
        if data[i] == target:
            return i
    return -1
data = [1,2,3,4,5,6,7]
print(search(data,7,4))

암시적 : 리스트 data의 인덱스는 0부터 n-1이라고 생각하고 시작 인덱스는 생략함.

def search(data,begin,end,target):
    if begin > end: # base case
        return -1
    elif target==data[begin]:return begin
    else: return search(data,begin+1,end,target) #begin이 1씩 늘면서 base case에 수렴한다.
data = [1,2,3,4,5,6,7]
print(search(data,0,6,4))

def search(data,begin,end,target):
    if begin > end:
        return -1
    elif target==data[end]:return end
    else: return search(data,begin,end-1,target) #end가 1씩 줄면서 base case에 수렴한다.
data = [1,2,3,4,5,6,7]
print(search(data,0,6,4))

명시적 : 시작과 끝을 begin과 end로 명시화했다.

매개변수의 명시화 : 최대값 찾기

def findmax(data,begin,end):
    if begin==end:return data[begin]
    else:
        return max(data[begin],findmax(data,begin+1,end))
data = [1,2,3,4,5,6,7]
print(findmax(data,0,6))

def findmax(data,begin,end):
    middle = (begin+end)//2
    if begin==end:return data[begin]
    else:
        max1 = findmax(data,begin+1,middle)
        max2 = findmax(data,middle+1,end)
        return max(max1,max2)
data = [1,2,3,4,5,6,7]
print(findmax(data,0,6))

이진 검색

def binarySearch(items,target,begin,end):
    if begin>end:
        return -1
    else:
        middle = (begin+end)//2
        result = target-items[middle]
        if result<0:
            binarySearch(items,target,begin,middle-1)
        elif result>0:
            binarySearch(items,target,middle+1,end)
        else:return middle
items=[1,2,3,4,5,6,7]
print(binarySearch(items,2,0,6))

왜 출력 값이 None이 나오는지 모르겠다.. ㅋㅋ...

출처 : https://www.inflearn.com/course-status-2/