[Kotlin] 알고리즘 - 재귀(Recursive)
Kotlin재귀(Recursive)
어떠한 것을 정의할 때 자기 자신을 참조하는 것
러시아 전통 인형인 마트료시카(큰 인형을 열면 안에 작은 인형이 나오며, 더 이상 인형을 담을 수 없을 때까지 계속된다)와 비슷하다.
재귀 알고리즘(Recursion Algorithm)
문제를 더 작은 문제로 분해하면서 연산을 분산시키는 방식
재귀 호출(Recursive Call)
알고리즘 내에서 자기 자신을 호출하는 방식
재귀 함수(Recursive Function)
함수 안에서 자기 자신을 호출하여 함수 내 로직을 반복 수행하는 함수
반복문(for, while)을 대체하여 가독성과 재사용성을 높일 수 있다.
규칙
문제를 단순화한다.
- 입력값과 출력값을 정의한다.
문제를 분할한다.
- 재귀 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대해 이루어져야 한다.
- 입력값을 기준으로 문제를 더 작은 문제로 분해한다.
종료 조건(Base Case)을 정의한다.
- 더 이상 반복(분해)되지 않는 가장 단순한 문제(종료 조건)에 도달할때까지 반복한다.
- 종료 조건을 명시하지 않으면 무한 루프에 빠진다.
kotlin
fun 재귀함수(input: 입력값 타입): 반환타입 {
// 종료 조건
if (input is 더 이상 분해할 수 없는 상태) {
return 가장 단순한 문제를 푼 결과
}
// 더 작은 문제로 분해하고 재귀 호출
val smallerInput = 더 작은 문제로 분해하는 과정
val result = 재귀함수(smallerInput)
// 결과 처리
// ...
return 결과
}한계
재귀 호출이 쌓일 수록 스택 메모리 영역에 너무 많은 공간이 할당되어 스택 오버플로(Stack Overflow)가 발생한다.
- Python: 재귀 호출 최대 깊이를 1천 번까지 허용하고 있다.
- JAVA: 코드와 스택에 할당된 가상 메모리의 양에 따라 차이가 있지만 약 1만 번까지 허용한다
대표적인 문제
피보나치 수(Fibonacci numbers)
- 첫번째 항과 두번째 항은 항상 1이며 그 뒤의 모든 항은 바로 앞 두 항을 합한 수열이다.
- n 번째 피보나치 수 = f(n) = f(n-1) + f(n-2)
kotlin
fun main() {
println(fibonacci(1)) // 1
println(fibonacci(2)) // 1
println(fibonacci(3)) // 2
println(fibonacci(4)) // 3
println(fibonacci(5)) // 5
println(fibonacci(6)) // 8
}
fun fibonacci(n: Int): Int {
if (n <= 2) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}팩토리얼(Factorial, 계승)
- 그 수보다 작거나 같은 모든 양의 정수의 곱
- n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱
- n! = n × (n-1) × (n-2) × ... × 1
kotlin
fun main() {
println(factorial(1)) // 1
println(factorial(2)) // 2
println(factorial(3)) // 6
println(factorial(4)) // 24
println(factorial(5)) // 120
println(factorial(6)) // 720
}
fun factorial(n: Int): Int {
if (n <= 1) return 1
return n * factorial(n - 1)
}Reference
https://ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion
https://sattlub123.medium.com/함수형-프로그래밍-재귀-함수-recursive-function-f5bf74fd280d
https://velog.io/@geesuee/자료구조와-알고리즘-재귀-zix72gv8
https://ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/properties-of-recursive-algorithms
https://about-tech.tistory.com/entry/Algorithm-재귀-알고리즘이란-recursion-algorithm
https://velog.io/@anjaekk/알고리즘-재귀함수Recursive-Function
https://velog.io/@kai6666/알고리즘-재귀-함수-Recursion
https://brunch.co.kr/@newnorm/129
