Kotlin - 재귀함수로 Fibonzcci(피보나치)수열 구현하기

kotlinexamples

피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다. 다음과 같은 패턴으로 반복됩니다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ....

루프를 이용한 구현

루프를 이용하여 간단히 구현할 수 있습니다. 앞의 두개의 숫자의 합이 다음의 값이 됩니다. 첫번째와 두번째 숫자는 1이고, 루프를 이용하여 계속 더해가면 됩니다.

fun fibonacciLoop(n: Int): Int {
    var first = 1
    var second = 1
    return when (n) {
        1 -> first
        2 -> second
        else -> {
            var current = first + second
            for (num in 3..n) {
                current = first + second
                first = second
                second = current
            }
            current
        }
    }
}

println("Loop - fibonacci(10) : ${fibonacciLoop(10)}" )
# 결과
Loop - fibonacci(10) : 55

재귀함수를 이용한 구현

피보나치수열은 재귀로도 구현할 수 있습니다. 재귀로 함수를 호출할 때마다 이전의 두 수의 합을 더하여 넘겨줍니다.

fun fibonacci(n: Int, first: Int, second: Int): Int {
    return if (n <= 0) {
        first
    } else {
        fibonacci(n-1, second, first + second)
    }
}

println("recursion - fibonacci(10) : ${fibonacci(10, 0, 1)}" )
# 결과
recursion - fibonacci(10) : 55

tailrec을 이용하여 성능 개선

tailrec은 꼬리재귀를 의미하며, 꼬리재귀인 함수에 이 키워드를 붙여주면, 코드가 빌드될 때 루프 형태로 변환됩니다. 즉, 구현은 재귀로 하지만 실제로 동작하는 것은 루프입니다. 재귀함수가 호출될 때마다 스택이 소모되어 성능에 좋지는 않습니다. 재귀로 구현하는 것이 편하신 분은 이 키워드를 사용하는 것이 재귀함수의 성능 문제를 해결할 수 있습니다. 하지만 이 키워드는 꼬리재귀에 대한 것만 가능합니다.

이렇게 키워드를 사용할 수 있습니다.

tailrec fun fibonacci(n: Int, first: Int, second: Int): Int {
    return if (n <= 0) {
        first
    } else {
        fibonacci(n-1, second, first + second)
    }
}

tailrec에 대한 자세한 내용은 Kotlin - tailrec(꼬리재귀)에 대해서 알아보기 를 참고해주세요.

Loading script...

Related Posts

codechachaCopyright ©2019 codechacha