Back to writing

코틀린

Table of contents

코틀린(Kotlin)에서의 재귀 함수

1. 반복문과 재귀 함수의 비교

프로그래밍에서 특정 작업을 반복적으로 수행할 때, 일반적으로 while 문이나 for 문과 같은 반복문을 사용합니다. 예를 들어, 1부터 n까지의 합을 구하는 코드를 while 문으로 구현하면 다음과 같습니다.

fun sumWhile(n: Int): Int {
    var sum = 0
    var i = 1
    while (i <= n) {
        sum += i
        i++
    }
    return sum
}

위 코드는 반복문을 사용하여 n까지의 합을 구하는 전형적인 방식입니다. 하지만 함수형 프로그래밍에서는 재귀를 활용하여 같은 문제를 해결할 수도 있습니다.

2. 함수형 프로그래밍 관점에서의 재귀

함수형 프로그래밍에서는 반복문 대신 재귀를 선호하는 경향이 있습니다. 이는 순수 함수(pure function) 의 개념과 불변성(immutability) 을 유지하기 위해서입니다. 재귀를 사용하여 같은 문제를 해결하면 다음과 같이 작성할 수 있습니다.

fun sumRecursive(n: Int): Int {
    if (n == 0) return 0
    return n + sumRecursive(n - 1)
}

위 함수는 n이 0이 될 때까지 자기 자신을 호출하면서 값을 더하는 구조입니다. 하지만 이 방식은 호출 스택이 계속 쌓이면서 스택 오버플로우(Stack Overflow) 가 발생할 수 있는 위험이 있습니다. 이를 해결하기 위해 코틀린에서는 tailrec 키워드를 제공합니다.

3. tailrec 키워드와 꼬리 재귀 최적화

코틀린에서는 꼬리 재귀(tail recursion) 를 최적화하는 tailrec 키워드를 제공합니다. 꼬리 재귀란, 함수가 자기 자신을 호출할 때 마지막 연산으로 호출 하는 경우를 의미합니다. 꼬리 재귀를 활용하면 컴파일러가 재귀 호출을 반복문으로 변환하여 스택 오버플로우를 방지 할 수 있습니다.

tailrec 사용 예제

tailrec fun sumTailRec(n: Int, acc: Int = 0): Int {
    if (n == 0) return acc
    return sumTailRec(n - 1, acc + n)
}

특징

  • tailrec 키워드를 사용하면 코틀린 컴파일러가 반복문으로 변환하여 최적화함.
  • tailrec 키워드는 반드시 꼬리 호출(tail call) 이어야 적용 가능함.
  • 스택 프레임(stack frame) 을 사용하지 않기 때문에 성능이 향상됨.

장단점

✅ 장점

  • 스택 오버플로우를 방지할 수 있음.
  • 반복문처럼 동작하면서도 함수형 스타일을 유지할 수 있음.

❌ 단점

  • tailrec 키워드는 일부 특정한 경우에만 적용 가능함.
  • 복잡한 연산에서는 tailrec을 적용하기 어려울 수 있음.

하지만 모든 경우에 tailrec을 사용할 수 있는 것은 아닙니다. 예를 들어, 여러 개의 재귀 호출이 존재하는 경우에는 tailrec을 사용할 수 없습니다. 이를 해결하기 위해 DeepRecursiveFunction 을 사용할 수 있습니다.

4. DeepRecursiveFunction을 활용한 재귀 최적화

코틀린 1.4부터 도입된 DeepRecursiveFunction은 더 깊은 재귀를 지원 하는 기능을 제공합니다. 이 기능은 코루틴을 활용하여 재귀 깊이에 제한 없이 사용할 수 있도록 도와줍니다.

DeepRecursiveFunction 사용 예제

import kotlin.coroutines.*
import kotlin.experimental.ExperimentalTypeInference
import kotlin.time.*

val deepSum = DeepRecursiveFunction<Int, Int> { n ->
    if (n == 0) 0 else n + callRecursive(n - 1)
}

    fun main() {
    println(deepSum(100000)) // 큰 숫자도 스택 오버플로우 없이 처리 가능
}

특징

  • DeepRecursiveFunction은 코루틴을 사용 하여 재귀 호출을 관리함.
  • 재귀 호출이 매우 깊어질 때도 스택 오버플로우를 방지 할 수 있음.
  • tailrec 키워드가 적용되지 않는 경우에도 사용할 수 있음.

장단점

✅ 장점

  • 매우 깊은 재귀에서도 안전하게 실행 가능.
  • tailrec이 적용되지 않는 경우에도 대체 가능.

❌ 단점

  • 성능이 tailrec보다 느릴 수 있음.
  • 사용법이 상대적으로 복잡함.

5. 결론

코틀린에서 재귀 함수는 다양한 방식으로 활용될 수 있으며, 상황에 맞게 적절한 최적화 기법을 사용할 필요가 있습니다.

  • 일반적인 재귀는 간결하지만 스택 오버플로우 위험 이 있음.
  • tailrec 키워드를 사용하면 반복문으로 변환되어 안전한 꼬리 재귀 최적화 가 가능함.
  • DeepRecursiveFunction을 사용하면 매우 깊은 재귀도 스택 오버플로우 없이 실행 가능 하지만 성능상의 trade-off가 있음.

따라서, 코틀린에서 재귀 함수를 사용할 때는 입력 크기, 성능, 가독성 등을 고려하여 적절한 방법을 선택하는 것이 중요합니다.