어떻게 재귀 함수

Question

의 스칼라를 두 번 전화를 최적화하기 위해 나는이 재귀 기능이 작동하도록하기 위해 노력하고있어 :

@tailrec 
def rec(n: BigInt): BigInt = { 
    if (n == 0) 0 
    else if (n == 1) 1 
    else (rec(n - 1) + rec(n - 2)) 
} 

Error:(13, 24) could not optimize @tailrec annotated method rec: it contains a recursive call not in tail position else (rec(n - 1) + rec(n - 2))

어떻게이는 tailrec와 함께 작동하도록 최적화 할 수 있습니까? 당신은 꼬리 재귀 도우미 함수를 작성해야 할거야

Answer 1

: 당신함으로써 만 얻을 수 있도록하는 기능으로 시퀀스의 이전 및 다음 값을 전달할 수 있도록

def rec(n: BigInt): BigInt = { 
    @tailrec 
    def helper(n: BigInt, previous: BigInt, next: BigInt): BigInt = { 
    if (n == 0) previous 
    else if (n == 1) next 
    else helper(n - 1, next, (next + previous)) 
    } 
    helper(n,0,1) 
} 

이있다 당신의 기능에 대한 하나의 호출.

많은 재귀 알고리즘은 추가 제어 흐름 메커니즘 (예 : 연속 전달)을 통해서만 꼬리 재귀 적으로 만들 수 있기 때문에 일반적인 패턴입니다. Factorial은 꼬리 재귀로 만들기 위해 추가 매개 변수로 도우미 함수를 작성해야하는 또 다른 좋은 예입니다.