다양한 재귀 함수를 꼬리 재귀로 변환하는 방법을 이해하려고합니다. 나는 피보나치와 팩토리얼을 꼬리 재귀로 변환하는 많은 예를 살펴보고 이해했지만 다소 다른 구조의 문제로 도약하는 데 어려움을 겪고 있습니다. 예 :
def countSteps(n: Int): Int = {
if(n<0) return 0
if(n==0) return 1
countSteps(n-1) + countSteps(n-2) + countSteps(n-3)
}
이것을 꼬리 재귀 구현으로 어떻게 변환 하시겠습니까?
다음과 같은 유사한 질문을 살펴 보았습니다. 일반 재귀를 꼬리 재귀로 변환 그러나 이것들은이 문제로 해석되지 않는 것 같습니다.
일부 는 꼬리 재귀 적이 지 않으며이를 변환하려는 시도는 결국 스택을 수동으로 구축하게됩니다.
그러나이 경우 누적 할 수 있습니다 (예상되지 않음, 스칼라 없음).
def countSteps(n: Int): Int = {
if (n < 0) return 0
countStepsAux(n, 0, 1, 0, 0)
}
def countStepsAux(n: Int, step: Int, n1: Int, n2: Int, n3: Int): Int = {
if (n == step) return n1
countStepsAux(n, step + 1, n1 + n2 + n3, n1, n2)
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다