컴파일러를 설계 할 때 처리 재귀를 처리해야합니까?

Question

함수 호출은 스택 데이터 구조를 통해 처리됩니다. 재귀를 지원하기에 충분합니까?

Answer 1

스택이 모두 인 경우는입니다. 재귀를 지원할 때는 컴파일러에서 특수 처리해야합니다.

이전 버전의 FORTRAN과 같은 이전 프로그래밍 언어에서는 런타임 환경에 함수 스택이 없으며 각 함수에는 메모리의 어딘가에 하나의 활성화 레코드가 예약되어있었습니다. 즉 재귀가 가능한 것은 아닙니다. 재귀 적으로 함수를 호출하면 활성화 레코드 하나를 덮어 쓰게되고 거기에 도착한 컨텍스트를 잃어 버리기 때문입니다.

함수 스택의 도입은 프로그래밍 언어에서 실제로 표현되는 재귀를 처음으로 활성화 한 것입니다. 그 전에 프로그래머는 재귀를 추상적으로 문제를 해결하는 도구로 사용하지만 호출 스택이 없기 때문에 반복적 인 논리로 코드를 변환해야합니다.

프로그래밍 언어가 재귀를 지원하려면 호출 스택을 동적으로 유지 관리하기위한 메커니즘이 필요합니다. 이는 명시 적 스택을 거칠 필요는 없습니다. 이론적으로 모든 스택 프레임을 동적으로 할당하고 링크 된 목록으로 함께 연결할 수 있습니다. 예를 들어 코 루틴이나 클로저를 지원하고 나중에 함수를 반환 한 후에 데이터를 나중에 저장할 수 있도록 이전 활성화 레코드를 유지해야하는 경우 유용합니다.

희망이 도움이됩니다.