피보나치 수열 문제와 같은 다이나믹 프로그래밍(Dynamic Programming) 문제를 functools의 lru_cache를 이용해 해결할 수 있다. 사용 방법은 간단하다. 점화식을 이용해 재귀 함수를 작성하고, 파이썬의 lru_cache 데코레이터(decorator)를 이용하여 함수가 반환하는 값을 메모이제이션(memoization)할 수 있다. 일반적으로 메모이제이션은 캐싱(caching)과 유사한 의미를 갖는다.

  흔히 다이나믹 프로그래밍 문제를 풀 때는 별도의 공간에 함수의 결과를 기록할 필요가 있는데, lru_cache를 사용하면 그럴 필요가 없어지는 것이다.

import sys
from functools import lru_cache

sys.setrecursionlimit(int(1e5))

@lru_cache(maxsize=None)
def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)


print(fibo(1000))

< 실행 결과 >

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875