[Kotlin] 16. 꼬리 재귀 함수

References: Do it! 코틀린 프로그래밍

코틀린에서 꼬리재귀함수에 대해 알아봅니다.

 

 

1. 재귀함수

 

꼬리재귀함수를 알아보기전에 재귀함수를 구현해봅시다.

아래는 팩토리얼의 예시입니다.

fun factorial(n: Int): Long = if(n == 1) n.toLong() else n * factorial(n-1)
fun main() {
    val num = 10
    val result: Long = factorial(num)
    println("Factorial: $num -> $result")
}

위의 factorial함수는 10번 호출되며 이 함수의 문맥을 유지하기위해 factorial()함수 스택 메모리의 10배만큼 메모리를 사용하게 됩니다.

만약 num이 큰값으로 설정된다면 실행 환경에 따라 스택 메모리가 부족해지는 문제를 겪을수 도 있습니다.

 

 

2. 꼬리 재귀 함수

 

코틀린에선 이러한 스택 메모리 문제를 방지하기 위해 꼬리 재귀 함수를 도입했습니다.

일반적인 재귀함수는 함수가 호출되고 계산이 이루어지지만 꼬리 재귀 함수에서는 계산을 먼저 하고 함수 호출이 이루어집니다.

따라서 꼬리 재귀 함수를 이용하기 위해선 계산이 먼저 이루어 지도록 함수를 작성해야 합니다.

코드를 다음과 같이 수정합니다.

tailrec fun factorial(n: Int, run: Int =1): Long = if(n==1) run.toLong() else factorial(n-1, run*n)
fun main() {
    val num = 10
    println("Factorial: $num -> ${factorial(num)}")
}

tailrec 키워드를 이용해 꼬리 재귀 함수를 만들었습니다.

factorial(n-1, run*n)는 인자 안에서 팩토리얼이 중간값을 계산하고 호출합니다.

꼬리 재귀 함수는 값을 그때그때 계산하므로 스택 메모리를 낭비하지 않습니다.

 

아래는 피보나치 수열을 일반 재귀 함수로 만든 예시입니다.

import java.math.BigInteger
fun recFibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger = if(n==0) a else recFibonacci(n-1, a+b, b)
fun main() {
    val num = 25000
    val first: BigInteger = BigInteger("0")
    val second: BigInteger = BigInteger("1")
    println(recFibonacci(num, first, second))
}

실행을 해보면 다음과 같은 결과값을 확인할 수 있습니다.

스택에 계속 쌓아 계산하므로 오버플로우 에러가 발생합니다.

이번엔 꼬리재귀함수로 수정해보겠습니다.

import java.math.BigInteger
tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger = if(n==0) a else fibonacci(n-1, b, a+b)
fun main() {
    val num = 25000
    val first: BigInteger = BigInteger("0")
    val second: BigInteger = BigInteger("1")
    println(fibonacci(num, first, second))
}

실행을 해보면 다음과 같은 결과값을 확인할 수 있습니다.

굉장히 긴 값이지만 정상적으로 동작하는것을 확인할 수 있습니다.