파이썬 2.7 - 재귀 피보나치 폭파

Question

피보나치를 계산할 때 fib1과 fib2의 두 가지 함수가 있습니다. 이 재귀 제한을 불면 때까지

def fib1(n): 
    if n < 2: 
     return 1 
    else: 
     return fib1(n-1) + fib1(n-2) 

def fib2(n): 
    def fib2h(s, c, n): 
     if n < 1: 
      return s 
     else: 
      return fib2h(c, s + c, n-1) 
    return fib2h(1, 1, n) 

fib2 잘 작동합니다. 올바르게 이해한다면, 파이썬은 꼬리 재귀를 최적화하지 않습니다. 그건 나에게 잘된다.

fib1은 매우 작은 값 n인데도 멈추기 시작합니다. 왜 그런 일이 일어나는거야? 그것이 부진하기 전에 어떻게 재귀 제한에 부딪치지 않는가?

Answer 1

기본적으로, 당신은 낭비를 많이 걸릴 기대. 당신은 쉽게 당신은 내가 기본 인자로 빈 딕셔너리를 사용하고 있음을 알 수 있습니다이

def fib1(n, memo={}): 
    if n in memo: 
     return memo[n] 
    if n < 2: 
     memo[n] = 1 
    else: 
     memo[n] = fib1(n-1) + fib1(n-2) 
    return memo[n] 

같은 기능을 memoize 수 있습니다. 동일한 dict이 모든 함수 호출에 대한 기본값으로 사용되기 때문에 이것은 일반적으로 나쁜 생각입니다. 여기

나는

을 계산 각각의 결과를 memoize 그것을 사용하여 해당 활용하고 할 수도 있습니다

이되는 n < 2 테스트

def fib1(n, memo={0: 1, 1: 1}): 
    if n in memo: 
     return memo[n] 
    else: 
     memo[n] = fib1(n-1) + fib1(n-2) 
    return memo[n] 

에게 필요 피하기 위해 0과 1로 메모 수상

def fib1(n, memo={0: 1, 1: 1}): 
    return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2)) 

Answer 2

각각의 재귀 트리를 생각해보십시오. 두 번째 버전은 함수 호출에 대한 매개 변수 계산에서 발생하는 재귀의 단일 분기입니다. 그런 다음 다시 값을 반환합니다. 앞에서 언급했듯이, 파이썬은 꼬리 재귀 최적화를 필요로하지 않지만, 꼬리 호출 최적화가 인터프리터의 일부라면 꼬리 재귀 최적화도 트리거 될 수 있습니다.

첫 번째 버전은 각 레벨에 2 개의 재귀 분기가 필요합니다! 따라서 함수가 잠재적으로 실행되는 횟수는 상당히 늘어납니다. 그뿐만 아니라 대부분의 작업이 두 번 반복됩니다! 다음을 고려하십시오. fib1(n-1)은 결국 fib1(n-1)을 다시 호출합니다. 이는 첫 번째 호출 프레임의 참조 지점에서 fib1(n-2)을 호출하는 것과 같습니다. 그러나 그 값이 계산 된 후에 다시 fib1(n-2)의 값에 추가되어야합니다! 따라서 작업은 불필요하게 여러 번 복제됩니다.

Answer 3

문제는 파이썬이 아니며 귀하의 알고리즘입니다. fib1은 tree recursion의 좋은 예입니다. 이 특정 알고리즘 (~ θ(1.6n)) 인 증명 here on stackoverflow을 찾을 수 있습니다.

n=30 (분명히 의견에 따르면)은 약 1/3 초가 걸립니다. 계산 시간이 1.6^n로까지 확장 할 경우, 우리는 n=100가 반복 n은 같은 값에 대한 fib1을 계산하여 시간에 대한 2.1 million years.