Kotlin 연습하기(4)-재귀함수

재귀 함수란 무엇일까?

재귀 함수란 자기 자신을 호출하는 함수이다. 즉, 문제를 해결하기 위해 동일한 문제의 더 작은 버전을 반복해서 호출하는 방식이다.

 

재귀 함수의 구성 요소

• 기본 조건(Base Case) : 재귀 호출을 멈추는 조건이다. 기본 조건이 없으면 함후가 무한히 자기 자신을 호출하게되는 무한루프에 빠지게 된다.
• 재귀 호출(Recursive Case) : 문제를 더 작은 문제로 나누어 자기 자신을 호출하는 부분이다.

 

 

재귀 함수 예제

1. 팩토리얼 계산(n!)

fun factorial(n: Int): Int {
    // 기본 조건: n이 0이면 1 반환
    if (n == 0) {
        return 1
    }
    // 재귀 호출: n * (n-1)! 계산
    return n * factorial(n - 1)
}

fun main() {
    val number = 5
    println("$number! = ${factorial(number)}") // 출력: 5! = 120
}

 

 

2. 피보나치 수열 계산

피보나치 수열은 앞의 두 수의 합으로 다음 수를 만드는 수열이다.

재귀적으로 f(n) = f(n-1) + f(n-2)로 정의되며, f(0)=0, f(1)=1 이다.

fun fibonacci(n: Int): Int {
    // 기본 조건: n이 0 또는 1이면 n 반환
    if (n == 0 || n == 1) {
        return n
    }
    // 재귀 호출: 피보나치 수열의 합 계산
    return fibonacci(n - 1) + fibonacci(n - 2)
}

fun main() {
    val n = 10
    println("Fibonacci($n) = ${fibonacci(n)}") // 예시 출력: Fibonacci(10) = 55
}

 

 

 

3. 문자열 재귀적으로 뒤집기

 - 문제 설명 : 문자열을 재귀 함수를 사용하여 뒤집는 코드를 작성해보자

 - 힌트 : 문자열의 첫 번째 문자와 나머지 부분을 분리하여, 나머지 부분을 재귀적으로 뒤집고 첫 번째 문자를 맨 뒤에 붙이는 방식으로 접근해보자

fun reverseRecursively(str: String): String {
    // 기본 조건: 문자열이 비어있으면 그대로 반환
    if (str.isEmpty()) {
        return str
    }
    // 재귀 호출: 문자열의 첫 번째 문자를 마지막으로 보내고, 나머지 문자열을 뒤집음
    return reverseRecursively(str.substring(1)) + str[0]
}

fun main() {
    val text = "Hello"
    println("원래 문자열: $text")
    println("뒤집은 문자열: ${reverseRecursively(text)}")
    // 출력: 뒤집은 문자열: olleH
}