두 가지 다른 재귀 방법

Question

두 가지 방법으로 fibonachi 행을 계산합니다. 왜 fib1이 fib2보다 훨씬 오래 실행됩니까?

public class RecursionTest { 

    @Test 
    public void fib1() { 
     long t = System.currentTimeMillis(); 

     long fib = fib1(47); 

     System.out.println(fib + " Completed fib1 in:" + (System.currentTimeMillis() - t)); 

     t = System.currentTimeMillis(); 

     fib = fib2(47); 

     System.out.println(fib + " Completed fib2 in:" + (System.currentTimeMillis() - t)); 

    } 


    long fib1(int n) { 
     if (n == 0 || n == 1) { 
      return n; 
     } else { 
      return fib1(n - 1) + fib1(n - 2); 
     } 
    } 


    long fib2(int n) { 
     return n == 0 ? 0 : fib2x(n, 0, 1); 
    } 

    long fib2x(int n, long p0, long p1) { 
     return n == 1 ? p1 : fib2x(n - 1, p1, p0 + p1); 
    } 
} 

출력 : 이유는 두 개의 알고리즘이 다른 런타임 복잡성이있다

2971215073 Completed fib1 in:17414 
2971215073 Completed fib2 in:0 

Answer 1

두 알고리즘이 완전히 다르기 때문에. 이것을 fib (5)로 보여 드리겠습니다. 당신이 호출하면

는 fib1는 (3), 나무와 그 시각화 할 수 있습니다 fib1 (4) 싶게 fib1 (5), 내부적으로 호출 :

 
    fib(5) 
/  \ 
fib(4) fib(3)

지금, FIB (4) 내부 FIB (3 호출) 및 fib (2).

내가 지금은이 어디로 매우 분명하다로 생각

 
      fib(5) 
     /  \ 
    fib(4)  fib(3) 
    /\  /\ 
fib(3) fib(2) fib(2) fib(1) 

, 당신은 나머지를 입력 할 수 있어야한다 :

그래서 지금 우리는이 있습니다.

편집 : 여기서 주목해야 할 또 다른 사실은 실제로 동일한 caclculation을 여러 번 수행해야한다는 것입니다. 이 그림에서 fib (2)와 fib (3)은 둘 다 여러 번 호출됩니다. 그리고 출발 수가 더 크면 더 나 빠지게됩니다. /편집

이제 fib2 (5)를 살펴 보겠습니다. 0으로 호출하면 0을 반환하고, 그렇지 않으면 fib2x (n, 0,1)를 호출합니다. 그래서 fib2x (5,0,1)를 호출합니다. fib2x (n, 0,1)는 이제 내부적으로 fib2x (n-1, p1, p0 + p1) 등을 호출합니다. 그래서, 볼 수 있습니다 :

   
fib2x(5, 0,1) => fib2x(4, 1,1) => fib2x(3, 1, 2) => fib2x(2, 2, 3) => fib2x(1, 3, 5) 

을 다음함으로써, 반환 상태에 도달하고

5. 그래서, 당신의 알고리즘이 완전히 다른 일을 반환합니다. 첫 번째는 재귀 적으로 그리고 위에서 아래로 작동합니다. 두 번째 것은 1에서 시작하여 그의 방식대로 작동합니다. 실제로, 반복적이어서 반복적입니다 (아마 당신을 끌기 위해 재귀 적으로 쓰여졌을 것입니다). 이미 계산 된 값을 버리지 않고 그대로 유지하므로 계산이 훨씬 덜 필요합니다.

Answer 2

: Ο(2ⁿ)

fib2가 Ο에에

• fib1 인을 (N)

Answer 3

fib1은 O (2^n) 런타임의 알고리즘입니다. fib2는 O (n) 런타임의 알고리즘입니다.

이 이유는 매우 차갑습니다. 이것은 메모 작성이라는 기술입니다. 프로그램이 수행하는 작업은 불필요한 계산을 피하면서 각 단계에서 저장됩니다.

당신은 루프 몇 단계 줄이기에 의해 발생 볼 수 있습니다 : 당신은 피보나치 시퀀스에서 임의의 숫자이 루프를 풀다 수

long fib2(int n) { 
    return n == 0 ? 0 : fib2x(n, 0, 1); 
} 
long fib2x(int n, long p0, long p1) { 
    return n == 1 ? p1 : fib2xy(n - 1, 1, 1); 
} 
long fib2xy(int n, long p0, long p1) { 
    return n == 1 ? p1 : fib2xyz(n - 1, 1, 2); 
} 
long fib2xyz(int n, long p0, long p1) { 
    return n == 1 ? p1 : fib2xyz(n - 1, p1, p0 + p1); 
} 

을; 각 단계는 n이 고갈 될 때까지 스택에 이전에 저장된 계산을 토대로 작성됩니다. 이는 모든 단계에서이 작업을 다시 실행해야하는 첫 번째 알고리즘과는 대조적입니다. 맵시 있는!

Answer 4

궁극적으로, fib2은 tail end recursion 만 사용하기 때문입니다. 결국 하나의 재귀 호출 만 수행합니다. 따라서 재귀와 관련된 "분기"가없고 선형 시간 솔루션이됩니다. 꼬리 호출이라는 사실은 재귀가 낮은 오버 헤드로 반복 프로 시저로 변환 될 수있는 특정 컴파일러/VM 최적화로 연결됩니다.

fib1은 실행 시간을 지수로 만드는 꼬리 호출 외에도 다른 재귀 호출을 사용합니다.