[코틀린으로 배우는 함수형 프로그래밍] 3장 재귀

fun repeat(n: Int) : Sequence<Int> = sequenceOf(n) + repeat(n)

안녕하세요 남갯입니다.

 

오늘은 코틀린으로 배우는 함수형 프로그래밍 3장 재귀에 대해 포스팅 해보려고합니다.

 

 

3.1 함수형 프로그래밍에서 재귀가 가지는 의미

재귀란? 재귀는 어떤 함수의 구현 내부에서 자기 자신을 호출하는 함수를 정의하는 방법을 말한다.

피보나치 수열의 경우 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) 로 정의된다.

즉 매번 호출된 자기자신을 통해 다음의 식들을 호출했기 때문에 이 점화식은 재귀이다.

 

피보나치를 통한 DP

 

    private fun fiboDynamic(n: Int, fibo: IntArray): Int {
        fibo[0] = 0
        fibo[1] = 1
        for (i in 2..n) {
            fibo[i] = fibo[i - 1] + fibo[i - 2]
        }
        return fibo[n]
    }

 

동적 프로그래밍을 통해 fibo의 만들어놓은 수열만큼의 크기와 n개의 값까지의 합을 구현했다.

 

피보나치 수열을 재귀로 표현

    private fun fiboRecursion(n: Int): Int = when (n) {
        0 -> 0
        1 -> 1
        else -> fiboRecursion(n - 1) + fiboRecursion(n - 2)
    }

이것에 대한 문제는 스택 오버플로우 에러가 발생한다. 실제 스택에 너무 많은 함수들이 쌓여서

 

함수형 프로그래밍에서 재귀

함수형 프로그래밍에서는 어떻게 값을 계산할 수 있을지 선언하는 대신 무엇을 선언할지 고민해야한다.

순수함수인 하스켈은 반복문을 제공하지 않지만 코틀린은 멀티패터다임 언어기 때문에 반복 명령어를 지원한다.

 

재귀의 특징

재귀자체는 간결하게 표현이 가능하지만

1. 동적프로그래밍에 비해 성능이 느리다.

2. 스택 오버플로우가 발생할 수 있다.

 

 

재귀의 설계법

fun helloFunc() {
        println("hello")
        helloFunc()
    }

    fun helloFunc(n: Int) {
        when {
            n < 0 -> return
            else -> {
                println("hello")
                helloFunc(n - 1)
            }
        }
    }

 

재귀 함수 설계 방법

- 재귀의 주의할점은 꼭 종료조건이 하나이상 존재

- 함수의 입력을 분할하여 어떤부분에서 호출할지를 꼭 정의해야한다.

 

fun func(n : Int) : Int = when{
        n < 0 -> 0
        else -> n + func(n-1)
    }

 

3-2 연습문제

X의 n승을 구하는 함수를 재귀로 구현해라

    fun practice1(x: Double, n: Int): Double {
        return when {
            n < 0 -> {
                (1 / x) * practice1(x, n + 1)
            }
            n == 0 -> {
                1.0
            }
            else -> {
                x * practice1(x, n - 1)
            }
        }
    }

 

3-3 연습문제

n 팩터리얼을 구하는 함수를 재귀로 표현

    fun practice2(n: Int): Int {
        if (n < 0) {
            return 0
        } else if (n == 0) {
            return 1
        }
        return n * practice2(n - 1)
    }

 

가장 큰 값 구하기

 

    fun List<Int>.head() = first()
    fun List<Int>.tail() = drop(1)

fun maximum(items: List<Int>): Int = when {
        items.isEmpty() -> error("")
        1 == items.size -> items[0]
        else -> {
            val head = items.head()
            val tail = items.tail()
            val maxVal = maximum(tail)
            if (head > maxVal) head else maxVal
        }
    }

확장함수를 통해 first와 drop을 만들었고 해당하는 값을 생성

 

 

리버스함수 구하기

 

    fun String.head() = first()
    fun String.tail() = drop(1)

    fun reverse(str : String) : String  = when {
        str.isEmpty() -> ""
        else -> reverse(str.tail()) + str.head()
    }

 

 

연습문제 3-4

10진수 숫자를 입력받아서 2진수 문자열로 변환하는 함수를 작성

    fun practice3(n: Int): String {
        if (n <= 0) {
            return ""
        }

        if (n / 2 <= 0 && n % 2 == 1) {
            return "1"
        }
        return "${practice3(n / 2)}${(n % 2)}"
    }

 

연습문제 3-5

숫자 두개를 입력받은 후 두번째 숫자를 첫번째 숫자만큼 가지고 있는 리스트를 반환하는 함수를 만들어보자.

 

    fun practice4(n : Int, element: Int) : List<Int>{

        return if(n <= 0){
            emptyList()
        }else{
            listOf(element) + practice4(n-1,element)
        }
    }

 

take 함수는 

입력 리스트에서 입력받은 숫자만큼 꺼내오는 take 함수

fun take(n: Int, list: List<Int>): List<Int> = when {
        n <= 0 -> list
        list.isEmpty() -> listOf()
        else -> listOf(list.head()) + take(n - 1, list.tail())
    }

 

연습문제 3-6

입력값 n이 리스트에 존재하는지 확인하는 함수를 재귀로 구현해보자

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

 

순수한 함수형 언어는 무한 자료구조를 지원하기 때문에 종료조건이 없으면 무한하게 동작하거나 무한한 자료구조를 만든다. 코틀린은 순수한 함수형 언어는 아니지만, 시퀀스를 활용하여 무한한 자료구조를 만들 수 있다.

 

 

repeat함수는

숫자를 입력받아 무한히 반복 호출하는 repeat 함수

fun repeat(n: Int): Sequence<Int> = generateSequence(n) { it }

fun repeat(n: Int) : Sequence<Int> = sequenceOf(n) + repeat(n)

 

연산자 재정의를 위한 repeat plus 재정의

    operator fun <T> Sequence<T>.plus(other: () -> Sequence<T>) = object : Sequence<T> {
        private val thisIterator: Iterator<T> by lazy { this@plus.iterator() }
        private val otherIterator: Iterator<T> by lazy { other().iterator() }
        override fun iterator(): Iterator<T> = object : Iterator<T> {
            override fun next(): T =
                if (thisIterator.hasNext())
                    thisIterator.next()
                else
                    otherIterator.next()

            override fun hasNext(): Boolean = thisIterator.hasNext() || otherIterator.hasNext()
        }

    }

 

    fun repeat(n : Int) : Sequence<Int> = sequenceOf(n) + {repeat(n)}

 

연습문제 3-7

take함수를 참고하여 repeat 함수를 테스트 하기 위해서 사용한 takeSequence 함수를 작성해보자. 그리고 repeat 함수가 잘 동작하는지 테스트해 보자.

 

 

zip 함수

두개의 리스트를 입력으로 받아서 하나의 리스트로 조합하는 함수 zip을 만들어보자.

 

    fun zip(list1 : List<Int>, list2 : List<Int>) : List<Pair<Int,Int>> = when{
        list1.isEmpty() || list2.isEmpty() -> listOf()
        else -> listOf(Pair(list1.head(), list2.head())) + zip(list1.tail(), list2.tail())
    }

 

연습문제 3-8

퀵정렬 알고리즘 함수를 작성해보자.

//todo

 

연습문제 3-9

최대공약수를 구하는 gdc 함수를 작성해 보자.

//todo

 

 

메모제이션으로 성능 개선하기

메모제이션은 어떤 반복된 연산을 수행할 때 이전에 계산했던 값을 캐싱해서 중복된 연산을 제거하는방법.

 

재귀적인 피보나치

재귀적인 피보나치는 자신이 2개의 함수를 호출되는데, 시간복잡도는 O(2^N)이 된다.

 

 

메모이제이션을 이용한 피보나치 수열

    fun fiboMemoization(n: Int): Int = when {
        n == 0 -> 0
        n == 1 -> 1
        memo[n] != -1 -> memo[n]
        else -> {
            println("fiboMemoization($n")
            memo[n] = fiboMemoization(n - 2) + fiboMemoization(n - 1)
            memo[n]
        }
    }

시간 복잡도는 O(N)으로 개선된다.

 

연습문제 3-10

factorial 함수를 메모이제이션을 사용해서 개선.

//todo

 

 

재귀의 문제점을 함수적으로 해결하기

메모제이션을 이용해 재귀의 효율성을 높이기는 했는데, 함수적인 해법인지 확인해야한다.

fun fiboFP(n: Int): Int = fiboFP(n, 0, 1)
    tailrec fun fiboFP(n: Int, first: Int, second: Int): Int = when (n) {
        0 -> first
        1 -> second
        else -> fiboFP(n - 1, second, first + second)
    }

메모제이션을 하지 않고 실제 매개변수로 받아서 캐싱하는 형태로 처리한다.

 

꼬리 재귀 최적화하기

꼬리 재귀 최적화란? 어떤 함수가 직간접적으로 자기 자신을 호출하면서도 그 호출이 마지막 연산인 경우를 말한다.

꼬리 최적화는 새로운 스택 프레임을 생성해서 재귀 호출하지 않고, 현재 스택 프레임에서 함수의 시작지점으로 점프하여 재귀 호출을 할 수 있다. 이 경우 재귀를 사용했지만 반복분(while, for)를 사용한것처럼 최적화 할 수 있다.

꼬리 재귀 최적화가 일어나면 메모이제이션과 같은 방법을 사용하지 않고도 성능을 향상시키고 스택 오버플로를 방지 할 수 있다.

 

tailrec fun findFixPoint(x : Double = 1.0) : Double{
        return if(x == cos(x)) x else findFixPoint(cos(x))
    }
    
    fun findFixPoint() : Double {
        var x = 1.0
        while(true) {
            val y = cos(x)
            if(x == y) return x
            x= y
        }
    }

연습문제 3.12

3-11에서 작성한 코드가 꼬리재귀인지 확인 하고 최적화되도록 수정

//todo

연습문제 3.13

연습문제 3-2에서 작성한 power 함수가 꼬리재귀인지 확인하고 개선해보자.

//todo

 

maximum 함수를 꼬리 재귀로 작성하기

꼬리재귀로 설계하는 방법도 일반 재귀를 설계하는것과 크게 다르지 않다.

 

   tailrec fun tailrecMaximun(items: List<Int>, acc: Int = Int.MIN_VALUE): Int = when {
        items.isEmpty() -> error("")
        items.size == 1 -> {
            println("")
            acc
        }
        else -> {
            val head = items.head()
            val maxVal = if (head > acc) head else acc
            tailrecMaximun(items.tail(), maxVal)
        }
    }

 

꼬리재귀는 스택을 사용하는게 아니라 내부적으로 스택이 아닌 반복문을 사용 가능하도록 변경해준다.

 

 

reverse 함수 꼬리재귀로 작성하기

tailrec fun reverse(str: String, acc : String = "") :String = when {
        str.isEmpty() -> acc
        else ->{
            val reversed = str.head() + acc
            reverse(str.tail(), reversed)
        }
    }

 

연습문제 3.14

3-4 toBinary 꼬리재귀로 변경

//todo

 

연습문제 3-15

3-5 replicate꼬리재귀 변경

//todo

 

 

take 함수 꼬리재귀로 작성하기

    tailrec fun take(n: Int, list: List<Int>, acc: List<Int> = listOf()): List<Int> = when {
        0 >= n -> acc
        list.isEmpty() -> acc
        else -> {
            val takeList = acc + listOf(list.head())
            take(n - 1, takeList)
        }
    }

 

꼬리재귀의 특징

- 누산값의 타입은 최종 반환값의 타입과 같다

- 종료조건의 반환값은 누산값이거나 누산값을 포함한 연산 결과이다.

- 중간 결괏값(take 함수에서는 takelist)를 만드는 순서는 보통 누산값 + 새로운 값이다.

 

연습문제 3-16

3-6 elem꼬리재귀 변경

//todo

 

zip함수를 꼬리재귀로 작성하기

    tailrec fun zip(
        list1: List<Int>,
        list2: List<Int>,
        acc: List<Pair<Int, Int>> = listOf()
    ): List<Pair<Int, Int>> = when {
        list1.isEmpty() || list2.isEmpty() -> acc
        else -> {
            val zipList = acc + listOf(Pair(list1.head(), list2.head()))
            zip(list1.tail(), list2.tail(), zipList)
        }
    }

 

상호 재귀를 꼬리 재귀로 최적화하기

 

상호재귀란?

상호재귀는 함수A가 함수 B를 호출하고 함수B가 다시 함수 A를 호출하는것을 말한다.

 

fun even(n : Int) : Boolean = when(n){
        0 -> true
        else -> odd(n-1)
    }
    fun odd(n: Int) : Boolean = when(n) {
        0 -> false
        else -> even(n-1)
    }

서로의 짝수 홀수의 함수들이 서로를 호출하고 있다. n의 갯수를 줄여가며 99999 -> 1의 값까지 호출

단 스택이 많이 쌓일경우 overflow

 

트램펄린

상호 꼬리 재귀를 가능하게 하려면 트램펄린을 사용하면 된다.

트램펄린은 반복적으로 함수를 실행하는 루프다. 이때 실행되는 함수를 성크라고 하는데, 성크는 다음에 실행될 함수를 매번 새로 생성하여 반환한다. 트램펄린에서 성크는 하나만 실행되고 프로그램을 성크로 쪼갠후 트램펄린을 점프하듯 반복 실행하면 스택이 커지는것을 막을 수 잇다.

 

    sealed class Bounce<A> {
        data class Done<A>(val result: A) : Bounce<A>()
        data class More<A>(val thunk: () -> Bounce<A>) : Bounce<A>()
    }
    
    tailrec fun <A> trampoline(bounce : Bounce<A>) : A = when(bounce) {
        is Bounce.Done-> bounce.result
        is Bounce.More -> trampoline(bounce.thunk())
    }

 

트램펄린이 끝마녀 bounce는 done이 되고 호출할것이 남았다면 more가 된다.

언어마다 표현이 다르지만 트램펄린은 종료조건을 의미하는 done과 다음 트램펄린에 성크를 넘기기 위한 more가 포함되어야한다.

trampoline함수를 보면 tailrec으로 꼬리재귀형태로 되어있어서 코틀린 컴파일러에 취적화한다.

 

    fun odd(n: Int) : Bounce<Boolean> = when(n) {
        0 -> Bounce.Done(false)
        else -> Bounce.More{ even(n-1)}
    }
    
    fun even(n : Int) : Bounce<Boolean> = when(n){
        0 -> Bounce.Done(true)
        else -> Bounce.More{ odd(n-1)}
    }

Even은 odd를 부르고 odd는 Even을 부르는 형태가 된다.

 

연습문제 3-18

trampoline 함수를 사용

//todo

 

연습문제 3-19

trampoline 함수를 사용 100000! 값

//todo

 

실전응용

멱집합을 구하는 함수 powerset를 구현해 보자. 먼저 powerset함수를 재귀의 조건에 맞게 작성

 

멱집합이란?

멱집합이란 어떤 집합의 모든 부분 집합의 집합이다. 집합의 S = {1,2,3} 이 있을때 S의 멱집합은

P(S) = {{},{1},{1,2},{1,3},{2},{2,3},{3},{1,2,3}} 이다.

P(S) 는 Set<Set<T>>가 된다. powerset 함수의 원형은

    fun<T> powerset(s : Set<T>): Set<Set<T>> = when {
        s.isEmpty() -> setOf(setOf())
        else ->{
            setOf(setOf())
        }
    }

 

재귀 본문을 작성해라

    fun <T> Set<T>.head() = first()
    fun <T> Set<T>.tail() = drop(1).toSet()
    fun<T> powerset(s : Set<T>): Set<Set<T>> = when {
        s.isEmpty() -> setOf(setOf())
        else ->{
            val head = s.head()
            val restSet = powerset(s.tail())
            restSet + restSet.map { setOf(head) + it }.toSet()
        }
    }

 

꼬리 재귀

    tailrec fun <T> powerset(s: Set<T>, acc : Set<Set<T>>) : Set<Set<T>> = when{
        s.isEmpty() -> acc
        else -> powerset(s.tail(), acc + acc.map{it + s.head()})
    }