스칼라 함수형 프로그래밍 - Tail recursion (꼬리 재귀 함수)의 이해와 활용. 함수형 프로그래밍 방식에서는 While loop 대신에 Tail recursion!!

View: 171 0 0
작성자: 달빛제이크
카테고리: Scala Language
발행: 2024-06-19 수정 2024-06-21

안녕하세요. 달빛제이크입니다.

이번 글에서는 Tail recursion 꼬리 재귀 함수에 대해서 알아 보겠습니다.

스칼라 함수가 제공하는 특별한 기능을 주제로 Repeated Parameter(반복 매개변수), Named arguments(이름 지정 인수), Default parameter values(기본 매개변수 값), SAM (Single Abstract Method, 단일 추상 메소드)에 이어서 Tail recusion(꼬리 재귀 함수)에 대해 이야기하려고 합니다.

1. Tail recursion (꼬리 재귀 함수)

함수형 프로그래밍 방식에서는 var을 사용하는 while loop 대신에 val을 사용하는 recursion(재귀 함수)을 주로 사용합니다. 특히 Tail recursion(꼬리 재귀 함수)은 while loop와 효율이 동일해서 재귀 함수를 사용해야 한다면 성능이 동일한 꼬리 재귀 함수를 사용해야 합니다.

예제를 먼저 살펴 보겠습니다.

// while loop
def approximateLoop(initialGuess: Double): Double =
  var guess = initialGuess
  while !isGoodEnough(guess) do
    guess = improve(guess)
  guess

// Tail recursion
def approximate(guess: Double): Double =
  if isGoodEnough(guess) then guess
  else approximate(improve(guess))

approximate 같이 마지막 수행에 자기 자신을 호출하는 함수를 Tail recursion(꼬리 재귀 함수)이라고 부릅니다.

보기에 코드가 매우 간단해졌고, 가독성이 좋아져서 코드의 의도가 명확해 보입니다. 다만 성능이 문제인데, 앞의 while loop는 함수 내부에서 실행이 되어, 함수를 여러 차례 반복 호출하는 아래 예제 보다 속도 면에서 빠를 것 같이 보입니다. 하지만 꼬리 재귀 함수에 한해서 스칼라 컴파일러가 최적화를 해주기 때문에 실제로 성능에서는 차이가 없습니다. 컴파일 된 Java bytecode를 확인해보면 while loop와 동일한 코드로 수행이 되며 자기 자신을 다시 호출하지 않고 내부 Looping을 통해 실행이 됩니다.

2. Tail recursion(꼬리 재귀 함수) 한계

컴파일러에서 최적화를 시켜주기 때문에 꼬리 재귀 함수의 형태에 제한이 있습니다.

• 꼬리 재귀 함수가 아닌 경우

def boom(x: Int): Int = 
  if x == 0 then throw new Exception("boom!")
  else boom(x - 1) + 1

위의 예제는 자기 자신을 호출한 후 1을 더했기 때문에 마지막 수행이 본인 호출이 아닌 + 1이 되어 재귀 함수이지만 꼬리 재귀 함수는 되지 못했습니다.
boom 함수를 실행하면 x + 1회 만큼 boom 함수가 호출 됩니다. 꼬리 재귀 함수로 만들기 위해 아래 예제와 같이 변경하였습니다.

def bang(x: Int): Int =
  if x == 0 then throw new Exception("bang!")
  else bang(x - 1)

꼬리 재귀 함수로 변경된 bang 함수를 실행하면 재귀 함수임에도 불구하고 한번만 호출이 되는 것을 확인 할 수 있습니다.

• 본인이 아닌 다른 함수를 호출하는 경우

예제를 먼저 보겠습니다.

def isEven(x: Int): Boolean = 
  if x == 0 then true else isOdd(x - 1)
def isOdd(x: Int): Boolean =
  if x == 0 then false else isEven(x - 1)

위의 예제는 두 개의 함수가 서로 번갈아 가며 호출하고 있어 재귀적으로 동작하기 때문에 재귀 함수이지만, 자기 자신을 호출하지 않고 다른 함수를 호출하는 경우이기 때문에 꼬리 재귀 함수가 아닙니다.

• 함수 리터럴

val funValue = nestedFun
def nestedFun(x: Int): Unit =
  if x != 0 then
    println(x)
    funValue(x - 1)

위의 예제는 nestedFun 함수를 Partially applied function으로 만들어 funValue 변수에 할당하였습니다. nestedFun이 runtime에서 Function value로 전환되고, nestedFun 함수 자체에서 마지막으로 호출하는 것이 본인이 아닌 이 Function value입니다. 따라서 이러한 경우에는 컴파일러가 꼬리 재귀로서 함수를 최적화 시킬 수 없는 상태가 됩니다.

꼬리 재귀 함수는 메소드 또는 내부 함수가 Function value나 다른 중개 함수를 거치지 않고 마지막 호출로 자기 자신을 직접 호출 할 때 최적화 될 수 있습니다.

함수형 프로그래밍 스타일로 코딩을 할 때 반복문에 대해서 꼬리 재귀 함수를 사용하도록 권장하고 있지만, 익숙하지 않으면 어렵게 느껴 질 수 있고 잘못 사용하면 성능을 떨어뜨릴 수 있습니다. 익숙해지기 위해서는 자주 사용해 보는 방법 밖에 없고, 성능을 떨어뜨리지 않기 위해서는 꼬리 재귀 함수만! 사용하면 됩니다.
꼬리 재귀 함수를 올바르게 사용한다면 성능을 동일하게 유지하면서 도메인에 집중한 코드 구현이 가능하고 코드가 간결해지며 따라서 가독성이 좋은 코드를 작성할 수 있습니다.

이상으로 Tail recursion 꼬리 재귀 함수에 대해서 알아 보았습니다.

감사합니다.