[Kotlin]꼬리 재귀 함수(Tail Recursive Function)

안녕하세요. 개발자입니다.

오늘은 코틀린에서 재귀함수의 문제점을 보완하기 위해 제시하는 방법인 꼬리 재귀 함수(Tail Recursive Function)에 대해서 다뤄보도록 하겠습니다.

꼬리 재귀 함수란?

재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태입니다.

기존 재귀함수는 모든 재귀 호출이 완료될 떄까지는 결과를 얻을 수 없었으나, 꼬리 재귀에서는 계산이 먼저 수행되고, 재귀 호출이 수행되는 구조입니다.

재귀함수, 꼬리 재귀 함수 차이점

꼬리 재귀 함수로 피보나치 구현하기

꼬리 재귀 함수를 이용해서 피보나치 수열의 n번째 항을 반환하는 fibonacci 함수를 만들어 주세요.

<<BigInteger 타입 사용>>

피보나치 수열의 간단 정리(좌 : 정의, 우 : 직관적 이해)

재귀 함수로 구현한 피보나치 수열

import java.math.BigInteger

fun main() {
    val n = 100
    val first = BigInteger("0")
    val second = BigInteger("1")
    println(fibonacci(n, first, second))
}

func fibonacci(n:Int, a:BigInteger, b:BigInteger):BigInteger{
	return if(n==0) a else fibonacci(n:n-1, b, b:a+b)
}

n값에 10,000을 넣으면 스택오버플로우 오류가 발생합니다.

꼬리 재귀 함수로 구현한 피보나치 수열

따라서 꼬리재귀함수 키워드를 작성하면 해결할 수 있습니다.

import java.math.BigInteger

fun main() {
    val n = 100
    val first = BigInteger("0")
    val second = BigInteger("1")
    println(fibonacci(n, first, second))
}

tailrec func fibonacci(n:Int, a:BigInteger, b:BigInteger):BigInteger{
	return if(n==0) a else fibonacci(n:n-1, b, b:a+b)
}

함수 앞에 tailrec이라는 키워드를 붙인 것뿐인데 스택오버플로를 해결할 수 있었습니다.