재귀 알고리즘 (Recursive Algorithm)

하나의 함수에서 자기 자신을 다시 호출하여 작업을 하는 것
종료조건이 꼭 있어야 한다.
ex) 자연수 총합 구하기

# recursive 방법
def sum(n):
	if n <= 1:
    	return n
    else:
    	return n + sum(n-1)

# iterative 방법
def sum(n):
	s = 0
    while n >= 0:
    	s += n
        n -= 1
    return s

위 두 방법 모두 시간복잡도는 O(n)이지만 iterative 방법을 사용하는 것이 더 효율적
why? recursive한 방법은 함수를 호출할 때 중복되는 연산을 하는 경우도 있으므로
ex) 팩토리얼

def factorial(n):
	if n <= 1:
    	return 1
    else:
    	return n * factorial(n-1)

ex) 피보나치 수열

# recursive
def solution(x):
    # 0, 1, 1, 2, 3, 5
    if x == 0 or x == 1:
        return x
    else:   
        return solution(x-2) + solution(x-1)

# iterative
def solution(x):
    # 0, 1, 1, 2, 3, 5
    if x == 1 or x == 0:
        return x
    f1 = 0
    f2 = 1
    for i in range(2, x+1):
        ans = f1 + f2
        f1, f2 = f2, ans
    return ans

ex) 재귀적 이진탐색

def solution(L, x, l, u):
    if l > u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid-1)
    else:
        return solution(L, x, mid+1, u)