내 코드가 Java에서 스택 오버플로 오류를 일으키는 이유는 무엇입니까? 그것은 결국 종료되어야합니다. for 루프 버전은 오류를 발생시키지 않습니다.

Question

update 10/23/2014 : 기본적으로 재귀 함수는 void 함수이므로 반환 이후에 더 이상 작업 할 필요가 없습니다. 재귀 재귀 버전과 동일해야합니다. 스택 오버플로가 발생해서는 안됩니다. 실제로 꼬리 재귀 비 void 반환 형식을 시도하고 여전히 스택 오버플로 오류가 발생했습니다. 나는 그것이 꼬리 재귀이지만 컴파일러 인터프리터가 어떻게 구현하는지에 달려 있다고 생각한다.

같은 코드의 for 루프 버전으로 인해 스택 오버플로 오류가 발생하지 않습니다. 그러나 아래의 코드 (재귀 버전) 않습니다. 본질적으로 그들은 똑같은 일을해야합니다. 루프 7000 (i = 7000)에서 예외 오류가 발생했습니다.

for 루프 버전이 아닌 동안 재귀 버전에서 오류가 발생하는 이유가 궁금합니다. 의심 스럽지만 확실하지 않습니다.

//recursive version, overflow 

public class Solution { 
    int n, low = -1, profit = 0; 
    int[] a; 

    public int maxProfit(int[] prices) { 
     n = prices.length; 
     if (n == 0 || n == 1) 
      return 0; 
     a = prices; 
     maxProfit(1); 
     return profit; 
    } 

    public void maxProfit(int i) { 

     if (i == n - 1) { 
      if (low != -1 && a[i - 1] <= a[i]) 
       profit += a[i] - low; 
      return; 
     } 
     if (a[i - 1] < a[i] && low == -1) { 
      low = a[i - 1]; 
     } 
     if (a[i - 1] > a[i] && low != -1) { 
      profit += a[i - 1] - low; 
      low = -1; 
     } 
     //System.out.print(i+","); 
     maxProfit(i + 1); 
    } 

    public static void main(String[] args) { 
     Solution sl = new Solution(); 
     // int[] a = { 1, 9, 6, 9, 1, 7, 1, 1, 5, 9, 9, 9 }; 
     // int[] a = { 4, 4 }; 
     // int[] a = { 3, 2 }; 
     // int[] a = { 1, 2, 3, 4, 3 }; 
     // int[] a = { 3, 2, 1, 0, 4, 5, 6, 7, 10, 4, 9, 7 }; 
     int[] a = new int[100001]; 
     for (int i = 0; i < 100001; i++) { 
      a[i] = 100000 - i; 
     } 
     System.out.println(); 
     System.out.println(sl.maxProfit(a)); 
    } 
} 

Answer 1

아무도 지금까지 정말

당신은 단순히 거기에 없을거야 함수를 호출

가 ... 무슨 일이 일어나고 있는지 설명하지 않았다 함수가 반환 될 때 그 정확한 지점으로

스택에 현재 상태를 저장하면됩니다 (한 방향으로 생성되는 메모리 영역). 앱이 반복 될 때마다 스택은 더 많은 메모리를 필요로하게됩니다.

스택 오버플로는 스택이 너무 커져 할당 된 메모리가 오버플로됩니다.

루핑 버전은 언제 돌아갈 것인지 기억할 필요가 없기 때문에 반복마다 여분의 메모리가 필요하지 않습니다. 단지 서클에서 돌아 다니며 계속 실행됩니다.

죄송합니다. 귀하가 요청한 것이 아니 었으면 미안합니다.

Answer 2

재귀 깊이는 100000 회입니다. 예, 무제한 스택 크기로 스택이 오버플로되지는 않지만 실제로는 스택 크기가 제한됩니다. 32 비트 VM의 기본 스택 크기는 64 비트 VM에서 320k 및 1024k입니다. 32 비트 VM에서 특정 기능은 콜 깊이 수준마다 스택의 64 비트를 사용합니다. 32 비트는 전달할 정수이고 32 비트는 리턴 주소입니다. 64 비트 * 100000 깊이 = 8 바이트 * 100000 깊이 = 800KB (약). 어느 것이 기본 스택 크기보다 훨씬 큽니다.

Answer 3

프로그램에 종료 조건이 없으므로주의해야합니다. 루프 maxhost (1)로 들어가지만 루프에서 빠져 나올 수있는 옵션이 없습니다.

업데이트 : 프로그램이 루프에 도착하면 이

public void maxProfit(int i) { 

    if (i == n - 1) { 
     if (low != -1 && a[i - 1] <= a[i]) 
      profit += a[i] - low; 
     System.out.println("i"); 
     return; 
    } 
    if (a[i - 1] < a[i] && low == -1) { 
     low = a[i - 1]; 
     System.out.println("i"); 
    } 
    if (a[i - 1] > a[i] && low != -1) { 
     profit += a[i - 1] - low; 
     low = -1; 
     System.out.println("i"); 
    } 
    //System.out.print(i+","); 

    maxProfit(i + 1); 
} 

Answer 4

내가 코멘트에 대답을 넣어 나타냈다는, 그것뿐만 아니라 합법적 인 답변을 할 수 있습니다 ..이 나올 수있는 방법이 없습니다. ..

재귀 함수는 기본 사례가 히트되지 않을 때 StackOverflowError를 발생시켜 스택을 푸는 경향이 있습니다. 이것은베이스 케이스 로직을 어지럽히거나,베이스 케이스쪽으로 움직이지 않거나, 너무 깊게 재귀하려고하는 것일 수 있습니다.

귀하의 경우에는 전화 스택이 100001 레벨 이상이므로 노력해야합니다. 거대합니다. 당신은 너무 많은 재귀 적으로 노력하고 있으며, 그것이 문제의 원인입니다. 당신은 어디 있었는지 정확히 기억이 있고 모든 변수가 너무 무엇인지 그것을 반환 할 수 있습니다 -