KO EN

[Kotlin] 알고리즘 - 재귀(Recursive)

by 민갤

Back End / Oct 16 2023

재귀(Recursive)

어떠한 것을 정의할 때 자기 자신을 참조하는 것

러시아 전통 인형인 마트료시카(큰 인형을 열면 안에 작은 인형이 나오며, 더 이상 인형을 담을 수 없을 때까지 계속된다)와 비슷하다.

재귀 알고리즘(Recursion Algorithm)

문제를 더 작은 문제로 분해하면서 연산을 분산시키는 방식

재귀 호출(Recursive Call)

알고리즘 내에서 자기 자신을 호출하는 방식

재귀 함수(Recursive Function)

함수 안에서 자기 자신을 호출하여 함수 내 로직을 반복 수행하는 함수

반복문(for, while)을 대체하여 가독성과 재사용성을 높일 수 있다.

규칙

문제를 단순화한다.

입력값과 출력값을 정의한다.

문제를 분할한다.

재귀 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대해 이루어져야 한다.
입력값을 기준으로 문제를 더 작은 문제로 분해한다.

종료 조건(Base Case)을 정의한다.

더 이상 반복(분해)되지 않는 가장 단순한 문제(종료 조건)에 도달할때까지 반복한다.
종료 조건을 명시하지 않으면 무한 루프에 빠진다.

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)

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

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)
}