코틀린으로 배우는 함수형 프로그래밍 연습문제 #3 [푸는 중]

[연습문제 3-2]
X의 n승을 구하는 함수를 재귀로 표현해보자.
함수의 선언 타입은 다음과 같다.
fun power(x: Double, n:Int): Double

fun power(x: Double, n:Int): Double {
    return when(n) {
        1 -> x
        else -> power(x*x, n-1)
    }
}

[연습문제 3-3]
입력n의 팩터리얼인 n!을 구하는 함수를 재귀로 구현해보자.

tailrec fun factorial(x: Int, result: Int = x): Int {
    return when(x) {
        1 -> result
        else -> factorial(x-1, result*(x-1))
    }
}

[연습문제 3-4]
10진수 숫자를 입력받아서 2진수 문자열로 변환하는 함수를 작성하라.
함수의 선언타입은 다음과 같다.
fun toBinary(n: Int): String

fun toBinary(n: Int): String {
    return when {
        n<=1 -> "1"
        else -> "${toBinary(n/2)}${n%2}"
    }
}

[연습문제 3-5]
숫자를 두 개 입력받은 후 두 번째 숫자를 첫 번째 숫자만큼 가지고 있는 리스트를 반환하는 함수를 만들어보자.
예를 들어 replicate(3, 5)를 입력하면 5가 3개 있는 리스트 [5, 5, 5]를 반환한다.
함수의 선언 타입은 다음과 같다.
fun replicate(n:Int, element: Int): List<Int>

fun replicate(n:Int, element:Int): List<Int> {
    return when(n) {
        1 -> listOf(element)
        else -> listOf(element)+replicate(n-1, element)
    }
}

[연습문제 3-6]

tailrec fun elem(num:Int, list:List<Int>):Boolean {
     return when {
         list.isEmpty() -> false
         list.first() == num -> true
         else -> elem(num, list.drop(1))
     }
}

[연습문제 3-7]

fun takeSequence(n: Int, sequence: Sequence<Int>): List<Int> {
    return when {
        n <= 0 -> listOf()
        sequence.none() -> listOf()
        else -> sequence.take(1).toList() + takeSequence(n-1, sequence)
    }
}

[연습문제 3-8] 퀵 정렬 구현하기

fun quickSort(pivot:Int, list:List<Int>): List<Int> {
    return when {
        list.isEmpty() || list.size == 1 -> list
        list.size == 2 -> when { // 배열에 두 개의 값만 남았을 때의 처리
            list[0] < list[1] -> list
            else -> listOf(list[1], list[0])
        }
        else -> {
            val partitionBasic = list.partition { it<pivot }
            val partitionAlter = list.partition { it<= pivot }
            val partition = when (partitionBasic.second != list) {
                true -> partitionBasic
                else -> partitionAlter
            } // 중복값에 대한 처리1

            val left = when {
                partition.first.isEmpty() -> listOf()
                partition.first.size == 1 -> partition.first
                partition.first == list -> list // 중복값에 대한 처리2
                else -> quickSort(partition.first[(partition.first.size)/2], partition.first)
            }
            val right = when {
                partition.second.isEmpty() -> listOf()
                partition.second.size == 1 -> partition.second
                else -> quickSort(partition.second[(partition.second.size)/2], partition.second)
            }

            left+right
        }
    }
}

배열 내에 중복값이 있을 경우 partition에 매개변수로 넘겨주는 함수 {it < pivot}를 사용하게 되면, pivot이 중복값일 때 회전이 되지 않기 때문에 무한루프에 빠져버리게 된다. 이를 방지하기 위해서 partitionBasic의 first값이 매개변수로 넘겨진 list와 동일할 경우에는, {it <= pivot}을 넘겨줘서 만들어진 partitionAlter를 사용한다. 예를 들어서 [2, 3, 1, 1]과 같은 배열에서 pivot으로 1이 선정됐을 때는, {it<pivot}을 할 경우 \[2, 3, 1, 1\], \[\] 페어가 생성되기 때문에 무한루프가 발생한다. 여기서 {it <= pivot}로 매개변수를 교체해주면, partition의 결과가 \[1, 1\],\[2, 3\]의 페어가 생성된다.

마찬가지로 위와 같이 중복값을 처리하게 되면, 최종적으로 중복인 배열들은 left를 처리할 때 {it <= pivot}에 의해 partition.first로 값이 몰리게 된다. 예를 들어 [1, 1, 1, 4, 3, 2]를 정렬할 때, left를 처리하는 과정에서 {it <= pivot}에 의해 [1, 1, 1], [] 배열에 인한 무한루프가 발생하게 된다. 이를 방지하기 위해 중복값에 대한 처리2와 같이 partition.first == list의 조건에서 list를 반환함으로써 종결조건을 만들어준다.

[연습문제 3-9] 최대공약수 구하기

fun gcd(m:Int, n:Int):Int = when (n) {
    0 -> m
    else -> gcd(n, m % n)
}

[연습문제 3-10, 11, 12] factorial 함수를 메모이제이션으로 개선하기

tailrec fun factorialMemoization(x:Int, acc:Int=1) :Int = when(x) {
    1 -> acc
    else -> factorialMemoization(x-1, acc*x)
}

[연습문제 3-13] power 함수를 꼬리 재귀로 개선하기

tailrec fun powerTailrec(x:Int, n:Int, acc:Int=1):Int = when(n) {
    0 -> acc
    else -> powerTailrec(x, n-1, acc*x)
}

[연습문제 3-14] toBinary 함수를 꼬리 재귀로 개선하기

tailrec fun toBinaryTailrec(x:Int, acc:String=""):String = when(x) {
    0 -> acc
    else -> toBinaryTailrec(x/2, "${x%2}$acc")
}

[연습문제 3-15] replicate 함수를 꼬리 재귀로 개선하기

tailrec fun replicateTailrec(n:Int, element:Int, acc:List<Int> = listOf()):List<Int> = when(n) {
    0 -> acc
    else -> replicateTailrec(n-1, element, listOf(element)+acc)
}

[연습문제 3-16] elem 함수를 꼬리 재귀로 개선하기
사실 얘는 list.drop(1)을 통해 list가 누산값을 대체하므로, 딱히 개선할 게 없긴 했다.

tailrec fun elemTailrec(n:Int, list:List<Int>):Boolean = when {
    list.isEmpty() -> false
    n == list.first() -> true
    else -> elemTailrec(n, list.drop(1))
}