TCO를 구현하는 언어에서 꼬리 재귀의 재귀 깊이를 제한합니까?

Question

테일 호출 최적화를 구현하는 언어에서 재귀 깊이에 대한 이론적/실제 제한은 무엇입니까? (되풀이 기능이 제대로 꼬리표로 붙어 있다고 가정하십시오).

재귀 프로 시저이지만 이론적 한계는 NONE입니다. 재귀 프로세스가 없기 때문에 추측 할 수 있습니다. 실질적인 한계는 주 메모리가 사용할 수 있도록 허용 된 것입니다. 내가 어딘가에 틀렸다면 명확히하거나 정정하십시오.

Answer 1

꼬리 재귀 함수가 최적화되면 본질적으로 반복 함수가됩니다. 컴파일러는 후속 호출에 대해 원래 호출의 스택 프레임을 다시 사용하므로 스택 공간이 부족하지 않습니다. 힙 메모리 (또는 스택에없는 다른 종류의 메모리를 할당하지 않는 경우)을 사용하면 무한히 깊게 (참을성이 있다면) 반복 할 수 있습니다. 무한 루프, 동일한 특성을 가짐).

요약하면 실용적인 제한은 없습니다.

Answer 2

@Mehrdad Afshari가 쓴 것 이외에도, 꼬리 재귀 (또는 일반적으로 꼬리 호출 체인)가 잠재적으로 무한 할 수 있다는 사실을 실제로 지적하고 싶습니다. 그렇지 않으면 쓸 수 없었기 때문입니다 웹 서버, 운영체제, 인터프리터, REPL, 또는 실제로 모든 종류의 이벤트 처리 루프를 기능 언어로 구현할 수 있습니다.

결국 운영 체제는 무한 루프 일 뿐이며 기능적 언어로 루프를 작성하는 방법은 꼬리 재귀를 사용합니다. 꼬리 재귀가 무한하지 않으면 루프는 무한하지 않습니다. 따라서 운영체제를 작성할 수있을뿐만 아니라 Turing-complete 언어가 될 수도 없습니다. 당신은 기능적인 언어로 웹 서버를 작성하는 방법

기본적으로, 이것이다 :

def loop(queue) = { 
    // handle first request in queue 
    loop(queue) 
} 

무한 꼬리 재귀없이를이 빠르게 메모리가 부족합니다.