글 읽기 - 재귀 깊이 초과(python3)

choisb7 4년 전 0

피보나치를 수식으로 구하는 식을 만들었습니다. 그 안에 combination이 필요한 부분이 있었습니다. n이 커지면combination에서 팩토리얼을 쓰는 과정에서 재귀 깊이 초과가 뜹니다. 어떻게 해결할 수 있을까요?

def fib(n):
    count = 0
    for k in range((n+1)//2):
        count += combination(n, 2*k+1) * (5**k)
    count = count // (2 ** (n-1))
    return count

faclist = {0:1, 1:1, 2:2}
def fact(n):
    if n in faclist:
        return faclist[n]
    else:
        faclist[n] = n * fact(n-1)
        return faclist[n]

def combination(n, k):
    return fact(n) // (fact(k) * fact(n-k))

h = 15 * (10 ** 5)

n = int(input())
n = n % h
print(int(fib(n))%1000000)