[Python] 재귀 함수란? (2)

목차

1. 메모(memo)
2. Early return
3. 리스트 평면화

 

---

메모(memo)

재귀 함수의 맥락에서 메모("memorandum"의 줄임말)는 비용이 많이 드는 함수 호출의 결과를 캐싱하고 재사용하여 재귀 알고리즘을 최적화하는 데 사용되는 메모이제이션이라는 기술을 말합니다. 이는 특히 함수에 겹치는 하위 문제가 있는 경우 재귀 함수의 성능을 크게 향상시킬 수 있습니다.

재귀 함수가 동일한 입력으로 여러 번 호출되면 동일한 결과를 반복적으로 계산하여 불필요한 오버헤드가 발생합니다. 메모이제이션은 이전 계산 결과를 사전이나 배열과 같은 데이터 구조에 저장하고 필요할 때 찾아봄으로써 이를 방지하는 데 도움이 됩니다.

재귀 함수에서 메모화를 구현하는 방법은 다음과 같습니다.

1. 이전에 계산된 하위 문제의 결과를 저장할 메모 테이블(일반적으로 딕셔너리 또는 리스트)을 만듭니다.
2. 특정 입력으로 재귀 함수가 호출되면 해당 입력에 대한 결과가 이미 메모 테이블에 있는지 확인하십시오.
3. 결과가 있으면 다시 계산하지 않고 메모 테이블에서 직접 반환합니다.
4. 결과가 없으면 평소대로 계산하고 결과를 메모 테이블에 저장한 후 반환합니다.

다음은 재귀 피보나치 함수에서 메모이제이션을 사용하는 예입니다.

def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}  # 메모 테이블 초기화

    if n in memo:
        return memo[n]  # 캐시 result 반환

    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)

    memo[n] = result  # Store the result in the memo table
    return result

n = 10
result = fibonacci_memo(n)
print(f"Fibonacci({n}) = {result}")  # Output: Fibonacci(10) = 55

이 예에서 fibonacci_memo 함수는 memo라는 사전을 사용하여 이전에 계산된 피보나치 수의 결과를 저장합니다. 이는 메모이제이션이 없는 순진한 재귀 구현과 비교하여 특히 n의 더 큰 값에 대해 함수의 성능을 크게 향상시킵니다.

---

Early Return

빠른 리턴(early retrun)은 함수가 끝에 도달하기 전에 함수에서 값을 반환하는 것을 나타냅니다. 이는 일반적으로 코드를 단순화하고 중첩된 조건문의 필요성을 줄이기 위해 수행됩니다. Early Return은 특정 조건이 충족될 때 함수가 일찍 종료되도록 하여 코드를 더 읽기 쉽고 이해하기 쉽게 만들 수 있습니다. Python에서 빠른 리턴을 사용하려면 함수 내의 어느 지점에서나 return 문을 사용할 수 있습니다.

다음은 Python 함수에서 조기 반환을 사용하는 방법을 보여주는 몇 가지 예입니다.

1. 숫자가 짝수인지 확인

  1) 빠른 리턴을 사용하지 않은 경우

def is_even(number):
    if number % 2 == 0:
        return True
    else:
        return False

print(is_even(4))  # Output: True
print(is_even(7))  # Output: False

  2) 빠른 리턴 사용하는 경우

def is_even(number):
    if number % 2 == 0:
        return True
    return False

print(is_even(4))  # Output: True
print(is_even(7))  # Output: False

2. 리스트에서 가장 작은 양수 찾기

  1) 빠른 리턴을 사용하지 않은 경우

def find_smallest_positive(numbers):
    smallest = None
    for number in numbers:
        if number > 0:
            if smallest is None or number < smallest:
                smallest = number
    return smallest

numbers = [3, -2, 7, 1, -5, 8]
print(find_smallest_positive(numbers))  # Output: 1

  2) 빠른 리턴 사용하는 경우

def find_smallest_positive(numbers):
    smallest = None
    for number in numbers:
        if number > 0:
            if smallest is None or number < smallest:
                smallest = number
        if smallest == 1:  # 가장 작은 양수가 1이라면 일찍 리턴(반환)합니다.
            return smallest
    return smallest

numbers = [3, -2, 7, 1, -5, 8]
print(find_smallest_positive(numbers))  # Output: 1

두 예제 모두 조기 반환을 사용하면 코드가 단순화되고 읽기가 더 쉬워집니다. 첫 번째 예에서는 'else' 문을 제거하고 짝수가 아닌 경우 함수에서 직접 'False'를 반환합니다. 두 번째 예에서 함수는 리스트의 나머지 부분을 확인할 필요 없이 값 1을 찾는 즉시 가장 작은 양수를 반환합니다.

---

리스트 평면화

리스트 평면화는 중첩 리스트(다른 리스트을 포함하는 리스트)을 단일 수준 리스트으로 변환하는 프로세스를 의미하며, 여기서 중첩 리스트의 모든 요소는 중첩 구조 없이 단일 리스트으로 병합됩니다. 즉, 리스트 평면화는 리스트들을 가져와서 한 수준으로 "평면화"하므로 결과 리스트에서 모든 요소에 직접 액세스할 수 있습니다.

중첩된 리스트가 다음과 같이 주어지는 경우를 예로 들겠습니다.

nested_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

리스트을 평면화하면 다음과 같은 결과가 발생합니다.

flattened_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Python에서 리스트을 평면화하는 방법에는 여러 가지가 있습니다. 다음은 리스트 평면화를 사용하는 예시입니다.

nested_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flattened_list = [item for sublist in nested_list for item in sublist]

print(flattened_list)  # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

이 예에서 중첩 리스트 [[1, 2, 3], [4, 5, 6], [7, 8, 9]]는 단일 리스트 [1, 2, 3, 4, 5, 6, 7, 8, 9]. 리스트 내포는 중첩된 리스트의 각 하위 리스트을 반복한 다음 하위 리스트의 각 항목을 반복하여 평면화된 리스트에 각 항목을 추가합니다.

 

다른 방법으로는 재귀 함수를 사용하여 입력 리스트을 재귀적으로 처리하고 해당 요소를 출력 리스트에 추가하는 방법이 있습니다. 요소가 리스트이면 함수는 해당 하위 리스트에서 재귀적으로 호출됩니다. 예를 들면 다음과 같습니다.

def flatten_list(input_list, output_list=None):
    if output_list is None:
        output_list = []

    for item in input_list:
        if isinstance(item, list):
            flatten_list(item, output_list)  # 하위 목록에 대한 재귀 호출
        else:
            output_list.append(item)  # 출력 리스트에 항목 추가

    return output_list


nested_list = [1, [2, 3], [4, [5, 6]], 7, [8, 9]]
flattened_list = flatten_list(nested_list)
print(flattened_list)  # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

이 예에서 flatten_list 함수는 입력 리스트(중첩 가능)과 선택적 출력 리스트을 사용합니다. 입력 리스트을 반복하고 요소가 리스트인 경우 해당 하위 리스트에 대해 재귀 호출을 수행합니다. 요소가 리스트이 아닌 경우 항목을 출력 리스트에 추가합니다. 출력 리스트은 입력 리스트의 모든 요소를 ​​처리한 후 반환됩니다.

중첩된 리스트 [1, [2, 3], [4, [5, 6]], 7, [8, 9]]는 단일 리스트 [1, 2, 3, 4, 5, 6, 7, 8, 9] 재귀 flatten_list 함수를 사용합니다.