https://www.acmicpc.net/problem/2747
2747번: 피보나치 수
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
처음 시도에서는 가장 보편적인 방법인 재귀를 통해서 문제풀이를 시도하였습니다. 하지만 시간초과의 결과가 나오게 되었습니다.
fun main() {
val n = readLine()!!.toInt()
fun fibo(n: Int): Int {
if (n == 0) return 0
if (n == 1) return 1
return fibo(n - 1) + fibo(n - 2)
}
print(fibo(n))
}따라서 재귀호출이 끝나고 현재 함수에서는 추가적인 연산을 하지 않게끔 해주어 마치 for loop와 동일한 효과를 발생하는 tailrec 키워드의 꼬리재귀를 사용하였습니다.
fun main() {
val n = readLine()!!.toInt()
tailrec fun fibo(n: Int , pre:Int, next:Int): Int {
if (n <= 0) return pre
return fibo(n - 1, next, pre +next)
}
print(fibo(n,0,1))
}매개변수로는 n-1 n-2 변수 대용으로 n-1 next와 이전에 계산한 합을 넘겨줍니다.