Java 재귀 메소드 Integer 객체를 사용하는 StackOverflowError

Question

필자는 fibonacci 시퀀스 반환에서 n을 반환하는 입력을 받으면 피보나치 수 반환기를 만들려고했습니다. 나는 그것을 재귀 적으로 만들고 공간의 복잡성을 낮추려고 노력했다. (나는 새로운 변수를 인스턴스화하지 않는다.) 나는 Integer 객체를 값으로 사용하며, 값의 오버플로 (음수 값을 반환 함)를 알고 있지만 실제로는 의도적으로 (교육용으로) 사용합니다. 함수는 다른 함수보다 공간 복잡성이 적기 때문에 smartestFib라고합니다.

문제는 smartestFib (n)을 130 이상으로 호출 할 때 발생합니다. 그것은 완벽하게 잘 작동 (오버플로 간주) 129 이하,하지만 130 이상에 대한 예외를 제공합니다. 주요 문제는 예외가 실제로 무엇인지 알 수 없다는 것입니다. 오류가 너무 많아서 처음 오류를 볼 수 없으므로 오류의 원인을 정확히 알지 못합니다. 나는 오류의 유형을 모르기 때문에 나는 그것을 잡지 못합니다.

내 코드는 다음과 같습니다

private static int smartestFib(Integer goalNum) 
{ 
    if (goalNum < 2) 
     return 1; 
    else 
     return smartestFib(goalNum-2, 0, 1,1); 
} 

private static int smartestFib(Integer goalNum, Integer currentNum, Integer lastValue, Integer beforeLastValue) 
{ 
    if (goalNum == currentNum) 
     return lastValue + beforeLastValue; 
    else 
    { 
     return smartestFib(goalNum, currentNum + 1, lastValue+beforeLastValue,lastValue); 
    } 
} 

문제의 임의성이 내가 모르고 나는 몇 가지 기술적 인 문제가 있는게 틀림 없어 때문에 나는이 문제에 어떤 도움을 주셔서 감사합니다 정말 것이며, 내가 단서가 없다 볼 곳. 미리 감사드립니다.

편집 : Apparently 수 있습니다 StackOverflowError, 많이 고마워! 하지만 이제는 궁금해합니다. 다른 기능이 더 높은 공간 복잡성을 가지고 있으며이 문제가 발생하지 않습니다. 방법?

private static int smarterFib(int goalNum) 
{ 
    assert (goalNum >= 0): "The variable goalNum may not negative."; 

    if (goalNum < 2) 
     return 1; 
    else 
    { 
     ArrayList<Integer> sequenceList = new ArrayList<Integer>(Arrays.asList(new Integer[] {1,1})); 
     return smarterFib(goalNum-2, sequenceList); 
    } 
} 

    private static int smarterFib(int goalNum, ArrayList<Integer> priorValues) 
{ 
    assert (goalNum >= 0): "The variable goalNum may not negative."; 
    assert (priorValues != null): "The array priorValues has not been initialized."; 

    if (goalNum <= priorValues.size()-2) 
     return (priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2)); 
    else 
    { 
     priorValues.add(priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2)); 
     return smarterFib(goalNum, priorValues); 
    } 
} 

이 하나가 문제 및 수행 나의 새로운 일이 발생하지 않는 이유는 볼 수 없습니다 ..

Answer 1

재귀 프로그램 & 더 만들어, 즉 (다시 같은 방법을 호출하고 이득 일 그 방법을 호출하는 스레드에 의해 stackframes) 그리고 기본 스택 크기에 도달하면 stackoverflowerror이됩니다.

문제를 해결하려면 -Xss을 JVM 인수로 전달하여 스택 크기를 늘려야합니다 (here).

다른 기능이 있으며 공간 복잡성이 더 높습니다.이 문제는 이 아닙니다. 방법?

그래서 1 차 및 2 차 프로그램의 차이는 아래에 설명 :

의 차이는 사람이 복싱을 사용한다는 것입니다 (당신은 goalNum 변수 Integer 유형을 사용하는 경우)와 다른 하나는 원시 int과 때를 사용 복싱을 사용하여 성능 문제가 발생하고 프로그램이 완료되지 못했습니다.

그래서 int에 Integer 유형에서 goalNum 변수를 변경 한 후 작동 (I 테스트) :

private static int smartestFib(int goalNum, int currentNum, 
    int lastValue, int beforeLastValue) { 
     System.out.println(goalNum); 
     if (goalNum == currentNum) 
      return lastValue + beforeLastValue; 
     else { 
      return smartestFib(goalNum, 
        currentNum + 1, lastValue+beforeLastValue,lastValue); 
     } 
} 

그래서, 요약, 항상 불필요한 복싱/언 박싱을 피하기 (프리미티브에서 변환하는 유형, 즉 랩퍼 , int에서 Integer까지)과 같이 광범위한 계산을 실행할 때 더욱 중요해질 수 있습니다.권투가 어떻게 문제를 일으키는 지에 대한 주제에 대한 자세한 내용은 here을 참조하십시오.

Answer 2

스택 오버플로는 루틴의 공간 복잡성을 기반으로하지 않습니다. 호출 스택의 공간에서 사용했음을 의미합니다. 모든 액티브 함수 호출은 스택 공간을 차지하고 전달 된 값을 추적하며 컨텍스트 스위칭 공간 (레지스터 값 등)을 유지합니다. (, 전체 메모리 사용은 N (goalnum) 즉 플러스 단어 쌍 오버 헤드 참조로 한 단어)

SmarterFib는 정수 (1 워드) 및 어레이를 통과한다. 총 스택은 2N입니다.

SmartestFib는 각 통화에 대한 네 개의 정수, 또는 스택에 4N 단어를 전달합니다.

나는 보통이 심각 서로 다른 런타임 스택 요구 사항이 기대하지 않을 것이다

: N은 = 260 (일부있을뿐만 전에 SmartestFib는 N = 130에서 스택을 불어 경우, 나는 SmarterFib 그것을 날려 기대 고정 된 오버 헤드).