재귀 알고리즘 (recursive algorithms)

1. 예제

# 1부터 n까지 모든 자연수의 합
sum(n) = sum(n-1) + n

# examples
> sum(1) = 1
> sum(2) = sum(1) + 2 = 3
> sum(3) = sum(2) + 3 = sum(1) + 2 + 3 = 6
> sum(4) = sum(3) + 4 = sum(2) + 3 + 4 = sum(1) + 2 + 3 + 4 = 10
> sum(5) = sum(4) + 5 = sum(3) + 4 + 5 = sum(2) + 3 + 4+ 5 = sum(1) + 2 + 3 + 4 + 5 = 15
> ...

2. 용어
종결 조건 (trivial case)
점화식 (recurrence formular)

3. 피보나치 순열

def fibo(x):
	if x <= 1: # 들여쓰기 주의! (그대로 쓰면 error)
    	return x
    else:
    	return fibo(x-1) + fibo(x-2)
        
# examples
> fibo(0) = 0
> fibo(1) = 1
> fibo(2) = fibo(1) + fibo(0) = 1 + 0 = 1
> fibo(3) = fibo(2) + fibo(1) = fibo(1) + fibo(0) + 1 = 1 + 0 + 1 = 2
> fibo(4) = fibo(3) + fibo(2) = fibo(2) + fibo(1) + fibo(1) + fibo(0) = fibo(1) + fibo(0) + 1 + 1 + 0 = 3
> ...

4. 반복적 알고리즘 (iterative algorithms)
재귀 알고리즘은 반복적 알고리즘보다 시간 효율이 떨어지지만 (∵함수 호출 반복), 알고리즘 이해에 유리.☆

5. 이진 탐색 비교

# 반복 (iterarive)
lower = 0
upper = len(L)-1
while lower <= upper:
	mid = (lower+upper)//2
    if L[mid] == x:
    	return mid
    elif L[mid] > x:
    	upper = mid-1
    elif L[mid] < x:
    	lower = mid+1
    return KeyError
    
# 재귀 (recursive)
def solution(L, x, lower, upper):
	if lower>upper:
    	return KeyError
    mid = (lower+upper)//2
    if L[mid] == x:
    	return mid
    #아래부터 재귀적 호출
    elif L[mid] > x:
    	return solution(L, x, l, mid-1)
    else:
    	return solution(L, x, mid+1, u)
      
    

한줄평

재귀적으로 문제를 푸는 건 쉽지만, 재귀적으로 사고하기가 넘나 어렵. 생각하다가 길 잃기 쉽상;