재귀 함수란 무엇일까?
재귀 함수란 자기 자신을 호출하는 함수이다. 즉, 문제를 해결하기 위해 동일한 문제의 더 작은 버전을 반복해서 호출하는 방식이다.
재귀 함수의 구성 요소
- 기본 조건(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
}'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글
| Kotlin 연습하기(6) - 선형/이진 검색 (0) | 2025.04.04 |
|---|---|
| Kotlin 연습하기(5) - 버블정렬 (0) | 2025.04.02 |
| Kotlin 연습하기(3) (0) | 2025.03.27 |
| Kotlin 연습하기(1) (0) | 2025.03.21 |
| 프로그래머스 - 3진법 뒤집기 (level 1) (0) | 2024.09.09 |
