[어서와! 자료구조와 알고리즘은 처음이지?] 02. 재귀 알고리즘

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다.

---

재귀 함수 (Recursive Function)

• 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
• 종결 조건이 매우 중요

1부터 n까지 모든 자연수의 합 구하기 예제

def recursive_sum(n):
    if n <= 1:  # 종결 조건
        return n
    return n + recursive_sum(n - 1)

def iterative_sum(n):
    result = 0
    while n >= 0:
        result += n
        n -= 1
    return result

Recursive	Iterative
O(n)	O(n)
직관적이지만 함수 호출과 같은 추가 비용이 들기 때문에 비효율적임	재귀함수에 비해 효율적임

팩토리얼 예시

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

피보나치 예시

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

재귀적 이진 탐색 예시

def recursive_binary_search(L, x, lower, upper):
    if lower > upper:
        return -1
    middle = (lower + upper) // 2
    if x == L[middle]:
        return middle
    elif x < L[middle]:
        return recursive_binary_search(L, x, lower, middle - 1)
    else:
        return recursive_binary_search(L, x, middle + 1, upper)