재귀함수(Recursion) 개념, 기본 예제

함수 안에 자기 자신을 재참조하는 방법

1. 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다
2. 모든 case는 base case로 수렴해야 한다
3. 암시적 매개변수를 명시적 매개변수로 바꿔야 한다

- 순차탐색에서 암시적 매개변수(처음 위치는 암시적으로 0부터 시작)

data = [0,2,4,6,8,10,11]
def search(data, n, target):
    for i in range(n):
        if data[i] == target:
            return i
    return -1
print(search(data,len(data),8))

 

- 순차탐색에서 명시적 매개변수(시작 위치, 끝 위치 명시적으로 표현)

data = [0,2,4,6,8,10,11]

def search(data, begin, end, target):
    if begin > end: # 길이가 0 인 경우(데이터가 없음)
        return -1
    elif target == data[begin]:
        return begin
    else:
        return search(data,begin+1,end,target)

print(search(data,0,len(data),8))

 

- 시작과 끝 중간 인덱스를 나눠서 찾는다

data = [0,2,4,6,8,10,11]

def search(data, begin, end, target):
    if begin > end: # 길이가 0 인 경우(데이터가 없음)
        return -1
    else:
        middle = (begin+end)//2
        if data[middle] == target:
            return middle
        index = search(data,begin,middle-1, target)
        if index != -1:
            return index
        else:
            return search(data,middle+1,end,target)

print(search(data,0,len(data),10))

 

- 최댓값 찾기(암시적)

data = [0,2,4,6,8,10,11]

def findMax(data,n):
    for i in range(1,n):
        result = max(data[0],data[i])
    return result

print(findMax(data,len(data)))

 

- 최대값 찾기(명시적)

data = [0,2,4,6,8,10,11]
def findMax(data,begin,end):
    if begin == end:
        return data[begin]
    else:
        return max(data[begin],findMax(data,begin+1,end))

print(findMax(data,0,(len(data)-1)))

 

- 최대값 찾기(중간값 기준)

data = [0,2,4,6,8,10,11]
def findMax(data,begin,end):
    if begin == end:
        return data[begin]
    else:
        middle = (begin + end)//2
        max1 = findMax(data,begin,middle)
        max2 = findMax(data,begin+1,end)
        return max(max1,max2)

print(findMax(data,0,(len(data)-1)))

 

- 이진탐색

data = [0,2,4,6,8,10,11]
def binarysearch(data,target,start,end):
    if start > end:
        return None
    else:
        middle = (start+end)//2
        if data[middle] == target:
            return middle
        elif data[middle] < target:
            return binarysearch(data, target, middle + 1, end)
        else:
            return binarysearch(data,target,start,middle-1)
print(binarysearch(data,12,0,(len(data)-1)))

 

- 재귀함수로 구현한 팩토리얼