pow 재귀 메서드에서 재귀 호출 줄이기?

Question

pow 메서드의 자체 구현에서 재귀 호출의 양을 줄이는 방법에 대한 질문이 있습니다. 여기 내가 쓴 것이 있는데, 이것이 향상 될 수 있는가?

public static int pow(double a, int b) { 
    boolean isNegative = false; 

    if(b < 0) { 
     isNegative = true; 
    } 

    if(b == 0) { 
     return 1; 
    } 
    else if(b == 1) { 
     return (isNegative ? (1/b) : b); 
    } 

    return (isNegative ? ((1/b) * (1/b) * pow(a, b + 2)) : (b * b * pow(a, b - 2))); 
} 

Answer 1

예, 개선 될 수 있습니다.

그것에 대해이 방법을 생각해

• B가 짝수이면, 다음^B = A^(b/2)^*는 (B/2).
• B가 홀수이면, 다음^B = A^(b/2) *는^* A는 (여기서, /하는 정수 나눗셈을 의미한다) (B/2).

코드 (뇌 컴파일, 커피 등, 아직 걷어하지 않은) :이 제공

public static double pow(double a, int b) { 
    if (b < 0) 
     return 1/pow(a, -b); 
    if (b == 0) 
     return 1; 
    double halfPow = pow(a, b/2); 
    if (b % 2 == 0) 
     return halfPow * halfPow; 
    else 
     return halfPow * halfPow * a; 
} 

는 O (로그 B) (N) O는 달리 재귀 호출에 귀하의 솔루션.

Answer 2

memoization을 살펴보십시오.

Answer 3

편집 : 기본적으로, 당신이있어 세 가지 문제 :

이

• 코드는 작동하지 않습니다
• 코드가 너무 복잡하다 (편집의로는, 지금은 완전히 a은 무시)
• 코드가 원하는 것 이상으로 반복되고 있습니다.

첫 번째 문제를 해결하지 않고 세 번째 문제를 수정하려고 시도하는 것이 무의미합니다. 전화의

첫 번째 포트는 일부 단위 테스트해야합니다. 그들은 당신의 코드가 현재 망가져 있다는 것을 매우 빨리 증명할 것이고, 그것을 고칠 때 그것을 바꿀 수 있고 당신이 무엇을 망가 뜨렸는지 알 수 있다는 자신감을 줄 것입니다.

그런 다음이를 단순화하는 것이 목표입니다.

if (b < 0) 
{ 
    return 1/pow(a, -b); 
} 

... 당신이 더 이상 b의 음의 값에 대해 걱정할 필요가 없습니다 예를 들어, 당신은 쉽게 귀하의 방법을 시작할 수 있습니다.

마지막으로을 사용하면 남아있는 것을 확인하고 반복적 인 솔루션을 반복적 인 솔루션으로 바꿀 수 있습니다.