🍒

꼬리 재귀(Tail Recursion)

꼬리 재귀(Tail Recursion)라고 해서 스택(Stack)에 함수에 대한 정보를 저장하지 않는 것은 아니다. 컴파일러가 꼬리 재귀에 대해 최적화를 하면서 반복문을 사용하도록 코드를 변경해준다.

꼬리 재귀가 정말 좋을까

꼬리 재귀 함수에 대한 정리를 보면 재귀 함수보다 더 좋다고 설명한다. 그런데 그 정리에서 이해가 가지 않는 부분이 더러 있다. 우연히 읽은 꼬리 재귀에 대한 글이다.

스택에 리턴 후 돌아갈 위치값을 저장할 필요도 없어진다.

글 마지막 부분에 위와 같은 문구가 있다. 시스템이 함수를 호출하는데 돌아갈 위치를 저장하지 않는다고 설명한다. 과연 그럴까, 꼬리 재귀에 대해 더 찾아봤다. 이 블로그 글에서는 다음과 같이 설명한다.

재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하도록 하는 방법으로 함수의 상태 유지 및 추가 연산을 하지 않기에 스택 오버 플로우 해결할 수 있다.

무언가 머리가 띵하다. 어떻게 함수를 호출해도 스택에 저장하지 않을 수 있을까. 내가 아는 범위에서는 함수를 호출하면 현재 함수 내의 지역 변수, 매개 변수, 다른 함수를 호출한 순간의 지점에 대한 정보를 스택에 저장하는 것으로 알고 있었다. 내가 틀렸을까. 위의 설명처럼 시스템이 꼬리 재귀 함수를 사용할 때에는 스택에 어떠한 정보도 저장하지 않을까?

재귀 함수(Recursion)

재귀 함수에 대해서 살펴보자. 재귀 함수에서 가장 중요한 부분은 마지막 종료 조건이다. 재귀 함수는 자기 자신(함수)을 재귀 호출하는데 마지막 종료 조건이 없다면 계속해서 자기 자신을 호출하기 때문이다. 정확히 말하자면 자기 자신을 계속 호출하다 스택 오버플로우(stack overflow)가 발생해서 프로그램이 죽는다. 마지막 종료 조건이 명확히 있어야 스택 오버플로우가 발생하지 않고 정상 종료할 수 있다. 그렇다면 마지막 종료 조건은 명확히 있지만, 그 조건을 달성하기 까지 재귀 호출을 많이 한다면 어떻게 될까?

스택 오버플로우는 말 그대로 스택에 데이터를 너무 많이 담아 넘쳐 흘렀다는 뜻이다. 이 의미를 생각한다면 마지막 종료 조건과는 상관없이 함수 호출을 계속한다면 스택은 넘쳐 흐를 것이다. 예를 들어, 스택의 크기가 100이라고 하자. 지금까지의 상황에서는 이 스택의 크기가 충분해서 스택 오버플로우가 발생하지 않았다. 그러나 새로운 상황에서 함수 호출을 한번 더 한다면 어떻게 될까? 결국 100 크기의 스택으로는 감당하지 못하여 스택 오버플로우가 발생한다. 다시 말하자면 재귀 함수를 사용할 때, 마지막 종료 조건이 명확하더라도 그 조건를 만족하기까지의 함수 호출이 너무 많다면 스택 오버플로우가 발생할 수 있다. 

재귀 함수와 꼬리 재귀 함수

123456789101112131415161718
fun main(args: Array<String>) {
    fun factorial(cursor: Int, n: Int): Int {
        if (cursor == n) {
            return n
        }
        return cursor * factorial(cursor + 1, n)
    }


    fun tailFactorial(cursor: Int, n: Int, result: Int): Int {
        if (cursor == n) {
            return result * n
        }
        return tailFactorial(cursor + 1, n, cursor * result)
    }


    println(factorial(1, 5))
    println(tailFactorial(1, 5, 1))
}

함수 factorial 는 이미 익히 알고 있는 재귀 함수다. 주요 부분은 함수의 맨 마지막 부분이다. cursor * factorial(cursor + 1, n) 를 보면 현재 함수의 cursor값과 재귀 호출한 결과 값을 사용해 연산을 하고 반환한다. 반면에 tailFactorial함수의 마지막 부분은 tailFactorial(cursor + 1, n, cursor * result)다. 함수의 반환 값을 또 다른 연산에 사용하지 않고 바로 반환한다. 

다시 말하자면, 일반적인 재귀 함수는 재귀 호출을 먼저한 후, 그 결과 값을 이용해 연산을 한다. 꼬리 재귀는 연산을 먼저한 후, 재귀 호출한다. 재귀 함수와 꼬리 재귀 함수의 차이는 확실히 보인다. 그런데 진짜 꼬리 재귀 함수로 구성하면 스택에 데이터를 저장하지 않을까? 꼬리 재귀라고 특별한 것이 있어서 스택 오버플로우를 겪지 않을 수 있는 것일까? 위의 블로그 글을 그대로 이해하면 저장하지 않아야 스택 오버플로우에서 자유로워 질 수 있다고 생각하지만, 기존의 함수 호출에 대한 스택의 개념을 뒤흔드는 상황이라 더 찾아보고 싶었다. 그러다 코틀린에서의 꼬리 재귀에 대한 글을 찾았다. 

꼬리 재귀 함수에 대한 최적화 작업

꼬리 재귀라고 스택에 함수에 대한 정보 저장을 하지 않는 것이 아니다. 컴파일러가 꼬리 재귀 함수를 최적화하여 반복문을 사용하는 코드로 변경해주는 것이다. 꼬리 재귀는 이 컴파일러의 최적화를 위해 사용하는 것이다. 다른 언어와 컴파일러가 최적화를 지원하지 않는다면 여전히 꼬리 재귀도 재귀 호출을 하고 스택 오버플로우에서 벗어날 수 없을 것이다.

12345678910111213
fun main(args: Array<String>) {
    fun loopFactorial(n: Int): Int {
        var cursor = 1
        var result = 1
        while (cursor <= n) {
            result *= cursor
            cursor += 1
        }
        return result
    }


    println(loopFactorial(5))
}

이 함수는 재귀 호출없이 반복문(loop)을 사용해서 팩토리얼을 구현한 함수다. 꼬리 재귀의 최적화 결과도 이렇지 않을까 추정해본다. 재귀 함수는 직관적으로 코드를 이해할 수 있어 자주 사용한다. 그러나 위의 상황처럼 맥락을 모르고 사용하면 문제가 발생할 수 있는 여지가 있다. 최적화를 믿고 꼬리 재귀나 반복문을 먼저 고려해보는 것은 어떨까.

마치며

취업 준비를 하면서 많은 면접을 경험했다. 한 면접에서 꼬리 재귀에 대한 질문을 받았었다. 처음 들어본 개념이고 재귀 함수에 대해 잘 알지 못했기 때문에 해당 질문에 답하지 못했다. 그러다가 이번에 알고리즘을 문제를 풀어보다가 우연히 꼬리 재귀에 대한 글을 읽었다. 이번에도 대수롭지 않게 글만 읽고 넘어 가기에는 발전이 없다고 느껴져서 한번 정리 해보았다.

References