꼬리 재귀 : 이가지 경우

Question

를 비교하는 이유는이 꼬리 재귀입니다 myList 매우 긴

def navigate(myList : List[Int]) : (Int, List[Int]) = { 
    navigate(0, 0, myList) 
} 

def navigate(step: Int, offset: Int, myList: List[Int]): (Int, scala.List[Int]) = { 
    if //some test and exit condition, then a definition of jump 
    else navigate(step + 1, offset + jump, myList) 
} 

경우, 첫 번째 경우는 어떤 문제를 제공하지 않습니다, 경우 두 번째 것은 StackOverflowError입니다.

또한 컴파일러가 재귀가 스택을 증가시키지 않도록 컴파일해야한다고 말하는 방법이 있습니까? 방법에 대한

위해

Answer 1

꼬리 재귀 최적화를위한 자격하기 위해서는해야합니다

• 이 꼬리 재귀 (! 대만족)
• 될 return
• 사용하지 final

두 예제 모두 # 1과 # 2를 따르지만 첫 번째 예제 만 # 3을 준수합니다 (로컬 메소드는 암시 적으로 최종적입니다).

가 final 수없는 경우 방법은 꼬리 재귀없는 이유는 "꼬리 재귀가" "꼬리 호출 자체"를 의미하지만,이 방법은 가상 경우에, 당신은 그 꼬리 여부을 알 수 없다 -calls 자체 또는 재정의 된 버전입니다. 컴파일 시간에 메소드가 재정의되었는지 여부를 파악하려면 클래스 계층 구조 분석이 필요합니다. Half Problem을 해결하는 것과 동등한 것으로 알려져 있습니다 ... IOW는 불가능합니다.

또한 컴파일러가 재귀가 스택을 증가시키지 않도록 컴파일해야한다고 말하는 방법이 있습니까?

아니요. 꼬리 재귀 최적화를 설정하거나 해제 할 수는 없습니다. tail-recursive (스칼라 언어 사양의 "tail-recursive"정의에 따라) 메서드는 항상으로 최적화되어 있습니다. 이 작업을 수행하지 않는 스칼라 구현은 스칼라 언어 사양을 위반 한 것입니다. 이

이이다, 그러나,이 주석과 주석이 방법은 꼬리 재귀의 SLS의 정의에 부합하지 않는 경우 컴파일러 오류가 발생합니다 것을 보장 scala.annotation.tailrec 주석.