재귀함수에 관한 고찰(Tail Recursion, Trampoline, reduce)

해당 내용은 애플 공식문서에서도 찾지 못하였고 stackoverflow와 여러 블로그 등 구글링 내용과 실험을 토대로 작성한 내용입니다 혹시 틀린부분이 있을 수 있으니 말씀해주시면 수정하도록 하겠습니다

재귀

• 꼬리 재귀와 트램펄린을 들어가기 전에 재귀에 대하여 간단하게 이야기 해보아야한다.
• 재귀란? 함수가 직접 혹은 간접적으로 함수 본인을 다시 호출하는 것을 재귀라고 표현한다.

func power(number: Int, n: Int) -> Int {
        if n < 1 { return 1 }
        return n * power(number: number, n: n-1) 
    }

• number의 n제곱을 구하는 함수로 지속적으로 n-1의 본인 함수를 호출하여 결과를 리턴하는 함수이다.

• 

• 해당 함수는 위와 같이 메모리 스택에 쌓이며 power(2, 10)의 형태를 실행한다면 power(2, 0)까지 각각의 함수가 스택에 쌓이고 마지막에 스택에 쌓인 power(2, 0)이 2 * power(2, 0)의 power(2, 0)을 참조하며 가장 밑에 있는 최종 power(2, 10)의 결과를 최종적으로 리턴하는 형태이다.

• 재귀함수는 일반적인 for 혹은 while과 같은 반복문과 다르게 간결하게 코드를 작성할 수 있다는 장점이 있다.

• 그러나, 메모리의 스택은 한정적으로 이런 재귀함수가 많이 쌓이다보면 결국에는 스택오버플로우라는 런타임에러가 뜨게 된다.

• 이런 방법을 해결하기 위해 Tail Recursion 꼬리 재귀라는게 등장한다.

꼬리재귀

• 꼬리재귀는 위와 같은 재귀의 문제점을 해결하기 위해 사용한다.
• 꼬리재귀는 리턴값을 단순하게 함수 하나로 리턴하는 형태를 가지는데, 그러면 스택에 쌓이는 구조는 똑같지 않을까? 라는 생각을 가지게 된다.
• 몇몇 언어의 컴파일러의 경우 해당 꼬리재귀를 컴파일 할 시 자동적으로 꼬리재귀라는 것을 알고 메모리에서 관리 할 수 있게 도와준다고 한다…..(해당 이야기는 밑에서 하기로 하고 우선은 꼬리재귀 구현을 해보도록하자!!)

func sumTail(n: Int, answer: Int = 0) -> Int {
    if n == 0 { return answer }
    return sumTail(n: n-1, answer: answer + n) 
}

• 위 예제는 1부터 n까지의 합계를 구하는 꼬리재귀함수이다.
• 해당 재귀함수의 인자에 현재 더한 값이 담기는 answer을 넣어줘서 함수만 리턴해주는 형식이다.

그런데

• 스위프트는 컴파일 단계에서 꼬리재귀를 메모리 관리해준다는 글들이 있고 ARC로 인해 가끔씩 안된다고 말하는 글들이 많다.
• 그런데 정말 단순하게 해당함수만 작성하여 실행하고 return answer에 브레이크를 걸어줘서 메모리를 확인한다면

null

• 위와 같이 메모리가 쌓이는 모습을 볼 수 있다
• 이것뿐만이 아니라 꼬리재귀라면 스택에 안쌓이므로 스택오버플로우가 발생하지 않아야하는데 700000이상의 값을 n에 넣는다면 스택오버플로우를 볼 수 있을것이다.
• 그렇기 때문에 트램펄린이라는 내용이 스위프트 재귀 관련 많은 글들에서 나오는것이며 트램펄린을 사용하면 스택에 두개 이상의 함수가 안쌓이고 아무리 큰 수라도 실행시간은 오래 걸려도, 절대 네버 스택오버플로우는 일어나지 않는다.

[iOS] 컴파일 최적화 feat 꼬리재귀

Writing High-Performance Swift Code

• 해당 블로그와 github문서를 보면 컴파일러를 통하여 꼬리재귀를 의도대로 컴파일 하여 실행시킬 수 있다.
• 컴파일 관련 최적화를 의미하는것 같은데 깃허브문서 내에서는 -Onone, -O, -OSize등이 있고 설명이 있고 해당 블로그에서는 꼬리재귀를 사용하기 위해 컴파일 항목을 변경하는 부분이 있는데 이를 실행해보면 꼬리재귀가 원래 의도대로 동작하는 것을 확인할 수 있다.
• 추후에 이 부분을 정리해봐야할 것 같다.

트램펄린(Trampoline)

Recursive Tail Calls and Trampolines in Swift - uraimo.com

• 트램펄린은 무엇일까??

• 

• 우리가 아는 트램펄린은 이렇게 점프할 수 있는 곳 방방이? 퐁퐁? 이런 이름으로 불리는 것인데 이것과 비슷하게 함수에서 함수로 점프한다? 라는 의미로 트램펄린이라는 명칭으로 사용되는 것 같다

• 트램펄린의 구현은 간단하게 작성할 예정이며 클로저와 @closure 등의 키워드를 사용하여 간단하게 만든 트램펄린 및 꼬리재귀 이 블로그에서도 사용할 예제들은 대부분 아래 링크에 있으니 한번 참고하면 좋을것 같다

• enum Result<T> { case Done(T) case Call(() -> Result<T>) }

• 간단하게 Result타입을 명시 했으며 해당 Result는 Done일 경우 최종적으로 값을 리턴해주는 case이며, Call의 경우 아직 답이 나오지 않았으므로 다시 함수를 호출하는 케이스이다.

func sumTrampoline(n: Int, acc: Int = 0) -> Int {
    func helper(n: Int, acc: Int) -> Result<Int> {
        if n < 1 { return .Done(acc)}

        return .Call({helper(n: n - 1, acc: n + acc)})
    }

    var res = helper(n: n, acc: acc)
    while true {
        switch res {
        case let .Done(r):
            return r
        case let .Call(f):
            res = f()
        }
    }
}

• 우선 함수 내의 helper은 위에 구현한 Result 타입을 반환하며 n < 1일 경우 Done 아닐 경우 Call과 그 안의 인자로 helper함수를 반환하여 준다.
• sumTrampoline함수는 해당 helper를 Done이 나올때까지 지속적으로 helper를 실행하고 Done이 나오면 Done안의 값을 리턴해주는 형태로 실행된다.

null

• 해당 sumTrampoline을 실행시킬 시 helper함수가 스택에 쌓이지 않고 지속적으로 실행되는 모습을 볼 수 있다.
• 또한, n의 값을 아무리 크게 주는경우 실행시간은 오래 걸리더라도 스택오버플로우는 발생하지 않고 값을 받아낼 수 있다.(1000000정도의 값을 시도해봐도 오래걸릴뿐 값을 받아낼 수 있다, 위에서 구현한 재귀와 꼬리재귀는 50만 정도만 되도 스택오버플로우가 걸리는것에 비해서 엄청난 모습이다)

애플이 제공해주는 메소드 reduce

Apple Developer Documentation

• 애플은 reduce라는 훌륭한 메소드를 제공한다.
• O(n)이라는 시간복잡도를 가진 메소드이지만 애플이 제공하기 때문에 reduce를 사용할 수 있다면 복잡하게 재귀, 꼬리재귀, 트램펄린 등을 구현하지 않고 reduce를 사용하는게 훨씬 좋은것 같다

let n = 1000000
let arr = Array(1...n)
let sumValue = arr.reduce(0, +)
print(x)    // print 500000500000

• 위와 같이 1000000이라는 큰 수도 거뜬히 계산하는 모습을 보여준다👍👍👍

재귀, 꼬리재귀, 트램펄린, reduce의 비교

• 비교는 CFAbsoluteTimeGetCurrent()을 사용하여 코드 실행시간을 나열할 것이고 일정 값 이상의 경우 스택오버플로우 때문에 꼬리재귀, 트램펄린과 reduce 두개만 비교를 할려고 한다.

n = 100일때

재귀 - 0.00013697147369384766
꼬리재귀 - 3.933906555175781e-06
트램펄린 - 1.0013580322265625e-05
Reduce - 2.0265579223632812e-06

• reduce > 꼬리재귀 > 트램펄린 > 재귀순으로 속도가 빠르다

n = 1000일때

재귀 - 0.0001360177993774414
꼬리재귀 - 4.0531158447265625e-06
트램펄린 - 6.604194641113281e-05
Reduce - 2.0265579223632812e-06

• reduce > 꼬리재귀 > 트램펄린 > 재귀순으로 n=100일때와 같다

n = 10000일때

재귀 - 0.0002899169921875
꼬리재귀 - 8.940696716308594e-06
트램펄린 - 0.0006979703903198242
Reduce - 7.987022399902344e-06

• reduce > 꼬리재귀 > 재귀 > 트램펄린 순으로 값이 커지니 재귀와 트램펄린의 시간이 약간 달라졌다.

n = 100000일때

재귀 - 0.0012589693069458008
꼬리재귀 - 4.494190216064453e-05
트램펄린 - 0.006783962249755859
Reduce - 5.4955482482910156e-05

• 꼬리재귀 > reduce > 재귀 > 트램펄린순으로 n=10000일때와 1, 2위가 달라졌다.

n = 10000000일때

• 해당 경우는 stackoverflow 런타임에러가 나기때문에 꼬리재귀, 트램펄린과 reduce만 비교하였다.
• 꼬리재귀 - 0.0035219192504882812 트램펄린 - 0.5289199352264404 Reduce - 0.004956960678100586
• 위의 경우에도 꼬리재귀이 빠른 모습을 보여주지만, 막상 값이 크니, reduce와 꼬리재귀는 이전값들 처럼 큰 차이를 보이지 않는다.
• reduce를 이용할 수 있다면 reduce를 이용하자.
• 만약, reduce를 이용할 수 없고 컴파일 설정을 만질 수 있다면 꼬리재귀를 이용하자!!

수정 2023.1.18.(수) - 꼬리재귀 컴파일 관련 내용 추가

수정 2023.1.20.(금) - 재귀, 꼬리재귀, 트램펄린, reduce비교 수정