recursive call with tailrec

tailrec fun pathFinder(grid: Array<String>, tNode : GNode, fromWhere : Direction, direction : Direction, pathLengh : Int, setMap : MutableMap<NodeCoordination, GNode>) {
            if(tNode.carvingRecord(fromWhere, direction)){ //available to move on next step
                //get next node
                val nextNode = tNode.nextNode(direction)
                //get next node direction
                val nextDirection = when(grid[nextNode.first][nextNode.second]){
                    's', 'S' -> {
                        when(direction){
                            Direction.UO -> { Direction.UO}
                            Direction.DO -> { Direction.DO}
                            Direction.RO -> { Direction.RO}
                            Direction.LO -> { Direction.LO}
                        }
                    }
                    'l', 'L' -> {
                        when(direction){
                            Direction.UO -> { Direction.LO}
                            Direction.DO -> { Direction.RO}
                            Direction.RO -> { Direction.UO}
                            Direction.LO -> { Direction.DO}
                        }
                    }
                    'r', 'R' -> {
                        when(direction){
                            Direction.UO -> { Direction.RO}
                            Direction.DO -> { Direction.LO}
                            Direction.RO -> { Direction.DO}
                            Direction.LO -> { Direction.UO}
                        }
                    }
                    else -> {
                        Direction.UO
                    }
                }
                pathFinder(grid, setMap[nextNode]!!, direction, nextDirection, pathLengh+1, setMap)
            }
            else //when the condition found the cyclic
            {
                if(pathLengh != 0) returnableList.add(pathLengh) // println(pathLengh)
            }
        }

 

출처 : https://codechacha.com/ko/kotlin-tailrect/

tailrec은 추가적인 연산이 없이 자신 스스로 재귀적으로 호출하다가 어떤 값을 리턴하는 함수를 의미함

 

자신만 반복적으로 호출하는 재귀함수(tailrec)는 while과 같이 루프를 사용하는 코드로 변환이 가능합니다. 이렇게 변환하면 좋은 점은 재귀함수가 호출되면서 소비되는 스택을 아낄 수 있다는 점입니다.

 

루프는 동일한 결과를 출력하면서 재귀함수보다 더 적은 자원을 사용하게 됩니다.

 

코틀린에서 tailrec 키워드가 있습니다. 이 키워드가 붙은 함수가 꼬리재귀 함수라면 코드가 컴파일될 때 루프를 사용한 코드로 변경됩니다.

재귀와 꼬리재귀 함수의 차이점에 대해서 알아보고, tailrec 키워드로 함수들이 어떻게 컴파일되는지 알아보겠습니다.

재귀함수와 꼬리재귀(tail recursive)

아래의 factorial은 재귀함수로 구현되었고, 재귀함수가 스스로 자신만을 호출하다 값을 리턴하는 구조이기 때문에 꼬리재귀(tailrec)라고 할 수 있습니다.

fun factorial(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

fun main(args: Array<String>) {
    println("factorial(10) : ${factorial(10, 1)}" )
}

반면에 아래 재귀함수는 꼬리재귀가 아닙니다. 자신만을 반복적으로 호출하지 않고 1 + 재귀함수와 같은 추가적인 연산을 수행합니다. 그렇기 때문에 꼬리 재귀함수가 아닙니다.

fun factorial_plus_n(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        1 + factorial_plus_n(n-1, n*acc)
    }
}