재귀 호출을 트램 폴린으로 변환하는 방법 이해하기

Question

최근에는 꼬리 호출을 제거하는 방법으로 trampolining에 대해 읽었습니다. 내 기능 중 하나를 trampolines을 사용하는 무언가로 변환하고 싶지만 힘든 시간을 보내고있다 (나는 OO 세계에서 온다).

특히 'More()'문을 작성하려는 두 가지 다른 재귀 호출이 있다면 괜찮습니까?

Answer 1

buildTree 메서드는 꼬리 호출을하지 않으므로 trampolining을 이용할 수 없습니다. Tail 호출은 메서드의 반환 값이 다른 메서드 호출의 결과 일 때의 최적화입니다. 스택 프레임을 호출 할 함수의 스택 프레임으로 바꿀 수 있습니다. 꼬리 호출 최적화가 없으면 재귀 함수 호출은 스택의 크기를 늘려 스택 오버플로를 초래할 수 있습니다. buildTree 메서드는 자체를 두 번 호출하지만 원래 스택 프레임은 남아 있어야하므로 두 함수 호출의 결과를 결합하여 Node을 새로 만들 수 있습니다.

JVM에는 꼬리 전체 최적화 기능이 내장되어 있지 않지만 스칼라에서는 함수가 자체 호출하는 꼬리 호출에 대한 해킹이 있습니다. Scala는 이러한 재귀 함수 호출을 함수의 시작 부분으로 건너 뛰기로 대체하여 효과적으로 재귀를 반복으로 바꾼다. 불행히도, 이것은 동시 재귀 호출 (예 : 메소드 A가 B를 호출하여 A를 호출 할 때)에는 작동하지 않습니다. 특별 모나드 (monad)를 기반으로 한 트램 폴리 라인 (trrampolining)이 여기에서, 또는 예외 처리를 남용하는 대신 사용될 수 있습니다. trampolining을 다른 곳에서 사용할 이유가 없습니다.