[3장 재귀] 3.5 꼬리 재귀로 최적화하기

코틀린으로 배우는 함수형 프로그래밍

꼬리 재귀 최적화: tailrec 을 활용

꼬리 재귀- 스택을 쌓으며 진행되는 재귀함수를 반복문으로 진행것과 같이(스택 프레임을 생성X) 컴파일러가 최적화할 수있도록 명시하는 것.

왜 사용하나? : 재귀는 호출이 반복되므로 깊이가 깊어지면 스택 오버플로우가 발생한다.

장점 : 메모이제이션 방법을 사용하지 않고도 성능향상, 스택오버플로우 방지.

조건 : 어떤함수가 직간접적으로 자기 자신을 호출하면서도 그 호출이 함수에서 마지막 연산일때!(그래서 꼬리 재귀)

-> 조건부분은 예시로 보시는게 빠르다.

꼬리 재귀 사용안하는 경우

/* 
	연습문제 3-5 : 숫자를 두 개 입력받은 후 두 번째 숫자를 첫 번째 숫자만큼 가지고 있는 리스트를 반환하는 함수를 
    만들어보자. 예를 들어 replicate(3,5)라고 입력하면 5가 3개 있는 리스트 [5, 5, 5]를 반환한다.
    함수의 선언 타입은 다음과 같다.
    fun replicate(n : Int, element : Int): List<Int>
*/
fun replicate(n : Int, element : Int): List<Int> {
	when {
		n < 0 -> return listOf<Int>()
        n == 1 -> return listOf<Int>(element)
        else -> {
        	return listOf<Int>(element) + replicate(n-1, element)
        }
	}
}

꼬리 재귀 사용하는 경우 

/*
	연습문제 3-15 : 연습문제 3-5에서 작성한 replicate 함수가 꼬리 재귀인지 확인해보자. 
    만약 꼬리 재귀가 아니라면 개선해보자.
*/
tailrec fun replicate_tailrec(n: Int, element: Int, replicated : List<Int>) : List<Int> {
    when {
        n < 0 -> return listOf<Int>()
        n == 1 -> return replicated + listOf<Int>(element)
        else -> {
            var newReplicated : List<Int> = listOf<Int>(element) + replicated
            return replicate_tailrec(n-1, element, newReplicated)
        }
    }
}

꼬리 재귀를 사용하는 경우(replicate_tailrec 함수)를 보았을 때, 함수의 마지막 연산이 다시 replicate_tailrec인 것을 볼 수 있다. 해당 조건을 만족해야 꼬리 재귀로 최적화가 가능하고 아니면 IDE에서 Warning을 보여준다.

꼬리 재귀를 사용할 때 함수의 특징은 인자에서 누적값을 가지고 있어야 한다는 점이다.

 

참고 문헌

코틀린으로 배우는 함수형 프로그래밍 (조재용, 우명인 지음) 인사이트