약 미리 경계 상황을 감지하여 재귀 시간을 단축하는 방법

Question

예를 들어, 교과서의 코드

- 재귀를 사용하여 피보나치 문제를 해결 -이 같다 :

cache = {} 

def fibo(n): 
    if n in cache : 
     return cache[n] 
    elif n <=2: 
     cache[n] = 1 
    else: 
     cache[n] = fibo(n-1) + fibo(n-2) 
    return cache[n] 

그러나, 나는 때마다 일을 걱정 함수 호출, 비용이 필요합니다. 왜 교과서는 불필요한 함수 호출을 피하기 위해, 대신에이 코드를 사용하지 않은 :

이런 식으로

cache = {} 

def fibo(n): 
    if n <=2: 
     cache[n] = 1 
    else: 
     # to avoid unnecessary function call 
     if n-1 in cache: 
      f1 = cache[n-1] 
     else: 
      f1 = fibo(n-1) 
     if n-2 in cache: 
      f2 = cache[n-2] 
     else: 
      f2 = fibo(n-2) 

     cache[n] = f1 + f2 

    return cache[n] 

, 우리는 실제로 그것을 호출하기 전에 불필요한 함수 호출을 피할 수 있습니다.

어쨌든 제 질문은, 교과서의 저자가 두 번째 방법으로 코드를 작성하지 않는 이유는 무엇입니까?

Answer 1

설명하는 내용은 dynamic programming입니다. 배열을 사용하여 재귀 단계 (ala memoization)를 저장하고 있습니다. 반복 당 하나 이상의 재귀 호출이있는 피보나치와 같은 경우 동적 프로그래밍이 실제로 선호되는 기술입니다.

교과서에서 왜 코드를 보여 주 었는지에 관해서는 저자가 너무 많은 개념을 한꺼번에 가지 않고 재귀를 보여주기를 원했기 때문에 가능성이 높습니다.