메모화로 재귀 함수의 효율성 높이기

재귀 함수는 자기 자신을 호출하는 함수로, 같은 계산을 반복하게 되어 성능이 저하될 수 있습니다.

이러한 문제점을 해결하기 위해 메모화(Memoization) 기법이 사용됩니다.

메모화는 함수의 반환 값을 저장해 두었다가, 같은 입력에 대해 함수를 다시 호출할 때 저장된 값을 반환하는 기법입니다.

메모화를 사용하면 함수의 반환 값을 저장해 두어 중복 계산을 방지하고, 함수의 실행 속도를 높일 수 있습니다.

복사
def fibonacci(n):
    # 메모이제이션에 사용할 빈 딕셔너리 생성
    memo = {}

    def helper(x):
        # 이미 계산된 값이 있으면 저장된 값을 반환
        if x in memo:
            return memo[x]
        # 종료 조건: 0 또는 1일 때 x 반환
        if x <= 1:
            return x
        # 계산 결과를 메모이제이션 딕셔너리에 저장
        memo[x] = helper(x - 1) + helper(x - 2)
        return memo[x]

    # 재귀 함수 호출
    return helper(n)

# 10번째 피보나치 수열 값 출력
print(fibonacci(10))
# 55

위 코드에서 memo 딕셔너리를 사용해 이전에 계산한 값을 저장하고, 이미 계산한 값이라면 저장된 값을 반환합니다.

딕셔너리에 담기는 값은 아래와 같은 n에 대한 피보나치 수열의 결과입니다.

복사
{
    2: 1,
    3: 2,
    4: 3,
    5: 5,
    6: 8,
    7: 13,
    8: 21,
    9: 34,
    10: 55
}

메모화를 사용하면 함수의 실행 속도를 높일 수 있으며, 중복 계산을 방지해 성능을 향상시킬 수 있습니다.

하지만 계산 결과를 저장해 두기 위한 추가적인 메모리가 필요하므로, 메모화를 사용할 때는 메모리 사용량에 주의해야 합니다.