무한 재귀 호출은이 경우 스택 오버플로를 발생시켜야합니까?

Question

최근 스택 오버 플로우의이 사건에 대해 생각했습니다 : 확실히 프로그램을 충돌

int f() 
{ 
    return f(); 
} 

int main(void) 
{ 
    f(); 
    return 0; 
} 

합니다. 하지만 내 질문은 왜 이것이 무한 루프와 같은 것이 아닌가? 컴파일러는 반환 라인에서 재귀 호출의 경우 호출 된 함수의 반환 점이 호출자의 반환 점이므로 호출하는 함수의 정보를 유지할 필요가 없음을 알 수 있습니다. 자,이 경우에 내가 컴파일러는 스택에 호출을 함수의 정보를 유지할 필요가 동의 누군가가 나에게 그것을 설명하면 내가 뭔가를 누락 확인을 위해

int f() 
{ 
    int x = f(); 
    return x; 
} 

int main(void) 
{ 
    f(); 
    return 0; 
} 

을, 나는 감사하겠습니다 . 감사합니다

Answer 1

일부 컴파일러에서는 올바른 최적화 플래그,이 실제로는 스택 오버플로가 발생하지 않습니다! 사실 g++에서 프로그램을 컴파일 해 보았습니다. 최적화가 기본값 인 경우 스택 오버플로가 발생하지만 최적화 수준이 -O3이면 무한 루프가됩니다.

무한 재귀와 무한 루프간에 차이가 나는 이유는 컴파일러가 기본적으로 이러한 구문을 구현하는 방법과 관련이 있기 때문입니다. 역사적으로 루프는 프로그램의 다른 부분에서 실행을 픽업하도록 지시하는 분기 명령을 사용하여 구현되었습니다. 이러한 모든 지침은 레지스터의 내용을 수정하는 다른 곳의 프로그램 카운터를 건너 뛰는 것입니다. 반면에 함수 호출은 스택에 새로운 활성화 레코드를 추가하여 인수, 반환 주소 등을 인코딩하여 함수가 반환 할 때 반환 할 위치를 알 수 있도록 구현됩니다.

즉, 이것은 함수 호출이나 분기를 구현해야하는 "방법"이 아닙니다. 이론적으로 컴파일러는 없지만 함수 호출과 리턴을 사용하여 루프를 구현할 수 있습니다. 비슷하게, 꼬리 재귀적인 (예를 들어) 함수의 경우, 컴파일러는 모든 스택 조작을 제거하고이를 순조롭게 분기 명령으로 변환하여 스택 설정 및 해체의 오버 헤드를 피할 수있는 경우가 많습니다.

즉, 다른 동작을하는 이유는 컴파일러가 코드를 구현하는 방법에 따라 달라집니다. 고비용의 함수 호출 셋업을 할 필요가 없다는 것을 알기에 충분히 똑똑하다면, 호출을 간단한 루프 명령으로 변환하고 영원히 반복 할 것입니다. 이것이 이것을 감지하지 못하면, 순진한 함수 호출 메커니즘으로 되돌아갑니다.

Answer 2

당신은 아무것도 놓치지 않았습니다. gcc -O2을 사용하여 프로그램을 컴파일하면 스택 오버플로가 발생하지 않습니다.

Answer 3

새로운 함수가 호출 될 때마다 여전히 스택에 프로그램 카운터를 푸시해야합니다. 이것이 각 함수 호출에서 스택이 커지는 이유 중 하나입니다.

Answer 4

내 생각 엔 C 컴파일러 작가는 아마

Answer 5

C는 꼬리 호출을 제거 할 필요가 없습니다 ... 그것은 매우 필요한 빈 기능에 무한 재귀 호출의 출력을 최적화 할 생각하지 않는다는 것입니다. (Scheme은 TCO을 수행해야합니다.)

Answer 6

필자는 실제로 컴파일러의 문제이며 어떻게 최적화되었는지 생각합니다. 두 경우 모두, while 루프와이 끝없이 반복되는 호출에서 기계 명령어가 가능한 한 명시 적으로 사용자의 희망 사항을 명령어로 변환하는 것으로 상상합니다. 아시다시피 while 루프의 경우 특정 위치로 돌아가서 계속 jmp로 돌아가고 있습니다. 재귀 호출을 사용하면 스택에 새로운 값을 넣을 수 있습니다. 따라서 질문에 따라 컴파일러가 얼마나 똑똑한 지 궁금합니다.