재귀 적 합계 스택 오버플로

Question

0에서 n까지 n의 합계를 계산하는 Java 재귀 적 메서드를 작성했습니다. 코드는 다음과 같습니다.

private static long sum (long n) { 
    if (n == 0) { 
     return 0; 
    } else { 
     return n + sum(n-1); 
    } 
} 

11000과 같은 큰 수를 전달하면 스택 오버플로가 가끔 발생합니다. 네, 가끔 말했죠. n이 11000보다 크거나 같으면 프로그램이 실행되고 응답 또는 스택 오버플로를 제공합니다.

아무도 무슨 일이 일어 났는지 설명 할 수 있습니까?

Answer 1

대신

public static long sum(long n) { 
    long result = 0; 
    for (int i = 1; i <= n; i++) { 
     result += i; 
    } 
    return result; 
} 

또는 물론, 당신은 단지 공상 공식 : _{감사 @Andy 터너}

public static long sum(long n) { 
    return n * (n + 1)/2; 
} 

이유를 사용할 수있는 For- 루프를 사용하는 것을 고려 당신은 JVM이 기대하는 것보다 큰 호출 스택을 생성하고 있기 때문에 StackOverflow 예외가 발생한다.

Answer 2

메서드를 호출 할 때마다 로컬 변수 및 메서드 매개 변수 등에 대한 참조를 저장하기 위해 해당 메서드 호출에 대한 호출 스택에 공간을 할당해야합니다.

스택은 주소 공간의 맨 위에 있으며 위에서 아래로 할당됩니다. 주소 공간의 하단에는 힙이 있으며,이 힙은 아래에서 위로 할당됩니다. 일단 메서드가 처리되면 스택에서 꺼내집니다.

기본적으로 메서드는 호출 할 때마다 스택에 메모리를 계속 할당하므로 호출이 너무 많으면 스택이 결국 힙으로 실행됩니다. 이 시점에서 이미 사용중인 메모리를 요청하려고 시도하고 스택 오버플로 형태로 세분화 오류가 발생하게됩니다.

이것은 재귀 구현이 일반적으로 대부분의 경우 권장되지 않는 이유 중 일부입니다.