코틀린 알고리즘 (자료구조) 1. 재귀

안녕하세요 Loner입니다. 오늘부터 코딩의 기본 소양이라고 할 수 있는 자료구조와 알고리즘에 대해 차근히 정리해가는 포스팅을 하려고 합니다. 저는 안드로이드 개발을 위주로 하기 때문에 객체지향과 함수형 파워를 가진 멀티 패러다임 언어 코틀린을 사용해서 자료구조에 대해 차근히 정리를 해볼려고 합니다.

코틀린 알고리즘 첫번째 이야기로 자료구조 및 알고리즘을 공부하다보면 반드시 한번쯤 들어봤을 그 이름 재귀에 대해서 한번 정리를 해볼려고 합니다. 

1.재귀 (Recursion)란?

재귀 호출(Recursive Call)이란 예를들어 A라는 함수가 있다고 가정했을 때, A함수 내에서 A함수를 호출해서 반복적으로 A함수를 여러번 호출하는 행위를 재귀라고 합니다. 이 재귀가 만약 A함수 내부에서 특별한 종료 조건을 만들지 않았을 경우 무한히 같은 함수를 호출하게 됩니다. 그래서 함수 내부에서 종료조건을 반드시 삽입 하는 것을 원칙으로 합니다.

(프로그래밍은 말로 풀어내면 낼수록 더 어렵게 설명이 되는거 같다. 코드를 봐서 어떤 개념인지 살펴보자.)

종료 조건이 없는 경우 코드 

fun main(){
    A()
}

private fun A(){
    A()
}

 

스택이 폭발 해버리는 스택오버 플로우 에러가 뜬다.

종료 조건이 있는 코드

fun main() {
    A(1000)
}

private fun A(number: Int) {
    println("$number")
    if (number == 0)
        return
    A(number - 1)
}

특정한 종료조건이 포함될 경우 에러가 나지 않는다.

위의 두 사례의 코드를 살펴보면 첫번째 코드는 A() 함수안에 다시 A() 함수를 호출합니다. 조건문을 포함하지 않았기 때문에 무한 반복에 빠져버리고 결국 스택이 터져서 에러가 발생합니다. 그래서 우리가 이 재귀를 이용하기 위해서 반드시 무한루프에서 벗어날 수 있는 어떤 조건을 설정을 해놔야합니다.

 

2. 재귀의 종류 

재귀도 종류가 있습니다. 주로 재귀 함수내에서 함수를 몇개 사용했는가, 혹은 어떤 방식으로 사용하는가로 나눕니다. 굳이 명칭을 신경쓰지 않고 재귀함수 내에서 개발자의 센스대로 마음가는대로 사용하는 경우가 있으나, 그래도 종류를 나눠 본다면 더 체계적으로 배울 수 있는 효과는 있는것 같습니다.

2-1. 선형재귀 (Linear Recursion)

선형 재귀는 가장 쉽게 많이 사용하는 형태입니다. 선형 재귀는 함수가 한번 호출 될때 딱 한번의 재귀가 일어나는 경우를 말합니다. 흔히 첫번째 값과 마지막 값을 다루는 경우에서 상당히 효과적이라고 볼 수 있습니다. 간단히 예제를 살펴보겠습니다. 

fun main() {
    intArrayOf(1,2,3,4,5).also {
        println(linearRecursion(it,5))
    }
}

private fun linearRecursion(A: IntArray, n: Int):Int {
    return if (n == 1) A[0] else linearRecursion(A, n - 1) + A[n - 1]
}

 

linearRecursion 함수는 인자로 IntArray와 Int를 받는 상태 입니다. 이 함수를 호출한 순서를 살펴보자면 다음과 같습니다.

이건 호출 순서일 뿐이다.

이런 순서로 내려오게 됩니다. 재귀를 한바퀴 돌때마다 조건으로 잡은 n이 1씩 감소됩니다. 그렇게 조건문에 가까이 다가면서 배열안에 있는 요소들을 하나씩 꺼내봅니다. 위의 그림처럼 n이 5에서 1를 향해 내려와 종료 조건에 맞게 되는 순간 그때 재귀의 아름다움이 폭발합니다.

마치 예비군 동원훈련을 끝낸 아저씨들이 훈련 끝나는 순간 빨리 뛰쳐나가는것처럼 마지막 종료조건에 도착했을 때 리턴이 되는 순간한꺼번에 리턴이 됩니다. 즉 모두 한번에 Pop이 된다는 얘기입니다. 재귀를 사용하는 경우 계속 스택에 함수 메모리가 쌓입니다. 스택은 먼저 들어온 데이터가 가장 늦게 나가는 구조입니다.

흔히 선입 후출이라는 말로 얘기를 합니다. 종료조건에서 리턴이 되는 순간 호출되는 함수들이 동시에 취소가 되고, 동시에 리턴이 되면서 5..4..3..2..1 순으로 쌓였던 것을 한번에 리턴합니다. 한꺼번에 리턴을 하기 때문에 1 + 2 + 3 + 4 + 5가 됩니다. 

음.. 상황이 억지긴 하지만 아무튼 내용이 전달 됬기를..

위에서 끝나는 소식은 1번이 듣고 5번이 가장 먼저 나가게됩니다. 그리고 다시 코드를 살펴본다면 재귀안에서 함수가 최대 한번만 호출되는데 저렇게 재귀 함수안에서 한번만 호출되는 것을 선형 재귀라고 부릅니다. 아마 재귀를 배우게되면 가장 첫번째로 배우게 되는 형태라고 생각이 듭니다.

2-2. 꼬리재귀

재귀 호출은 알고리즘을 사용하는데 있어서 좋은 방식입니다. 하지만 문제를 호출하기 위해 선형 재귀를 사용하다 보면 이전의 호출들을 기억하기 위해서 컴퓨터의 메모리를 사용해야합니다. 그래서 재귀 호출이 많으면 많을 수록 사용되는 메모리의 용량도 매우 큽니다. 

꼬리 재귀는 재귀호출 이후에 어떠한 연산도 하지 않도록 메모리 사용면에서 효율적인 재귀 알고리즘 입니다.이러한 문제를 해결해줍니다.  하나의 예시를 보도록 하겠습니다.

fun main() {
    intArrayOf(1,2,3,4,5).also{
        tailRecursion(it,0,4)
    }
}
private fun tailRecursion(A:IntArray , number1:Int, number2:Int){
    if(number1<number2){
        val temp = A[number1]
        A[number1] = A[number2]
        A[number2] = temp
        tailRecursion(A,number1+1,number2-1)
        return
    }
    A.forEach {println(it)}
}

거꾸로

IntArray 배열안에 포함된 요소들의 순서를 역순으로 바꿨습니다. (물론 코틀린 콜렉션 함수중에 리버스 함수를 사용한다면 꼬리재귀를 사용하지 않아도 되지만 연습용이니 넘어갑시다) 변수 temp에 A[number1]를 할당 하고  A[number1]에 A[number2]로 할당하고 A[number2]에 temp가 할당이 됩니다. 그리고 선형 재귀의 예시와 달리 재귀 함수 리턴값과  계산하지 않습니다. 

이렇게 되면 마지막 함수 호출에서 리턴하는 값이 호출 재귀 함수와 반환값이 동일하게 되는것이 꼬리 재귀의 특징입니다.

A[2]는 딱 중간지점

 

2-3 이중재귀

알고리즘이 재귀호출을 두번 호출 할 때 이중 재귀라고 부릅니다. 같은 문제를 반으로 나눠 풀어나갈 때 많이 사용하는 재귀 방식이라고 합니다. 빠르게 예시를 들어보도록 하겠습니다. 예시를 보면 함수 안에 재귀 호출을 두번 호출 한다는것이 무엇인지 바로 확인 하실겁니다.

fun main() {
        println(binaryRecursion(10))
}
fun binaryRecursion(k: Int): Int {
    return if (k == 1 || k == 0) k else binaryRecursion(k - 1) + binaryRecursion(k - 2)
}

그 유명한 피보나치 수열을 통해 1에서 10까지의 합을 구했습니다. 코드를 보시면 함수안에 두개의 재귀 함수가 같이 있는것이 보일겁니다. 저런 방식으로 함수 내의 두개의 재귀 함수를 사용하는 것을 이중재귀라고 합니다. 두개의 함수를 이용하기 때문에 두개의 문제를 나눠 계산하기 매우 효율적이라고 합니다.

3. 마무리

오늘은 알고리즘 재귀에 대해 정리를 해봤습니다. 사실은 선형재귀, 꼬리재귀, 이중재귀 말고도 다른 유형이 더 있긴 하지만 대표적으로 많이 쓰이는 종류를 찾아봤습니다. 알고리즘 얘기가 나오면 꼭 잊을만하면 언급되는 재귀 입니다. 실제 안드로이드 개발 할 때에 반복문을 자주 쓰는게 현실이지만 기본 소양으로 알아두면 좋을 법한 녀석입니다.

이렇게 오늘도 한번 정리를 해봤습니다. 흔히 자료구조 및 알고리즘은 현실적으로 봤을 때, 취업을 준비하는 개발자분들이 많이 준비하시는 것으로 알고 있습니다. 우연히 이 포스팅을 읽었다면 응원 한마디 전달해드리고 싶습니다. 모두 화이팅 하시길 바랍니다.