재귀적 사고

재귀는 함수 정의를 통해 컴퓨터가 수행할 작업을 명확히 지시합니다. 함수형 프로그래밍에서는 재귀 개념이 광범위하게 사용됩니다.
다음은 재귀 함수의 몇 가지 예시입니다.

object RecursiveExample extends App {
  // 리스트 합계 구하기
  def sum(xs: List[Int]): Int =
    if (xs.isEmpty)
      1
    else
      xs.head + sum(xs.tail)

  // 최댓값 찾기
  def max(xs: List[Int]): Int =
    if (xs.isEmpty)
      throw new NoSuchElementException
    else if (xs.size == 1)
      xs.head
    else
      if (xs.head > max(xs.tail)) xs.head else max(xs.tail)

  // 문자열 뒤집기
  def strReverse(xs: String): String =
    if (xs.length == 1)
      xs
    else
      strReverse(xs.tail) + xs.head

  // 퀵 정렬
  def quicksort(ls: List[Int]): List[Int] = {
    if (ls.isEmpty)
      ls
    else
      quicksort(ls.filter(_ < ls.head)) ::: ls.head :: quicksort(ls.filter(_ > ls.head))
  }
}

위 코드에서 마지막 퀵 정렬 함수를 보면, 재귀 방식으로 구현되어 코드가 매우 간결하고 이해하기 쉽습니다. 재귀 함수의 핵심은 재귀 표현식을 잘 설계하고 알고리즘의 경계 조건을 결정하는 것입니다. 위 퀵 정렬에서는 빈 리스트가 정렬된 리스트라고 가정하는 것이 경계 조건이며, 이 조건이 재귀를 종료시키는 신호입니다.

꼬리 재귀

재귀 알고리즘은 호출 스택을 유지해야 하므로 효율성이 떨어지며, 호출 횟수가 많아지면 메모리 부족이나 스택 오버플로우가 발생할 수 있습니다. 그러나 꼬리 재귀는 이러한 단점을 극복할 수 있습니다.
꼬리 재귀는 재귀 호출이 함수의 마지막 문장이고, 그 결과가 직접 반환되는 특별한 재귀 호출 형태입니다. 재귀 결과가 항상 직접 반환되므로 꼬리 재귀는 반복문으로 변환하기 쉬우며, 컴파일러가 쉽게 최적화할 수 있습니다.

팩토리얼 계산의 고전적 예제

일반 재귀로 구현한 코드는 다음과 같습니다.

def factorial(n: BigInt): BigInt = {
  if (n <= 1)
    1
  else
    n * factorial(n - 1)
}

위 코드는 n-1의 팩토리얼을 재귀 호출할 때마다 추가적인 곱셈 연산이 필요하므로, 스택의 데이터를 모두 유지해야 합니다. 새로운 재귀마다 새로운 함수 스택이 할당됩니다.
실행 과정은 다음과 같습니다.

factorial(4)
--------------
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * factorial(1)))
4 * (3 * (2 * 1))

반면, 다음은 꼬리 재귀 버전으로, 효율성 측면에서 반복문과 동등합니다.

import scala.annotation.tailrec

def factorialTailRecursive(n: BigInt): BigInt = {
  @tailrec
  def loop(acc: BigInt, n: BigInt): BigInt =
    if (n <= 1) acc else loop(acc * n, n - 1)

  loop(1, n)
}

실행 과정은 다음과 같습니다.

factorialTailRecursive(4)
--------------------------
loop(1, 4)
loop(4, 3)
loop(12, 2)
loop(24, 1)

이 함수의 loop는 마지막 단계에서 경계 조건 값을 반환하거나, 재귀 함수 자체를 호출합니다.
꼬리 재귀 버전으로 변환하는 핵심:
꼬리 재귀 버전에서 가장 중요한 것은 적절한 누산기(acc)를 찾는 것입니다. 이 누산기는 마지막 재귀 호출에서 스택에 남아 있는 데이터를 보존하고, 이전 호출 결과를 축적하여 스택 데이터를 폐기할 수 있게 하며, 현재 함수 스택을 재사용할 수 있게 합니다.
이 예제에서 변수 acc가 바로 누산기로, 재귀 호출마다 갱신되며 경계 조건이 충족되면 그 값을 반환합니다.
Scala는 꼬리 재귀를 위해 특별히 @tailrec 어노테이션을 제공합니다. 이 어노테이션은 프로그래머가 올바른 꼬리 재귀 함수를 작성했는지 확인하며, 실수로 꼬리 재귀가 아닌 함수를 작성하면 컴파일 오류를 발생시켜 코드 수정을 유도합니다.

피보나치 수열 예제

원래 코드는 간단합니다.

def fibonacci(n: Int): Int =
  if (n <= 2)
    1
  else
    fibonacci(n - 1) + fibonacci(n - 2)

꼬리 재귀 버전은 두 개의 누산기를 사용합니다. 하나는 작은 항(acc1)을 저장하고, 다른 하나는 큰 항(acc2)을 저장합니다.

def fibonacciTailRecursive(n: Int): Int = {
  @tailrec
  def loop(n: Int, acc1: Int, acc2: Int): Int =
    if (n <= 2)
      acc2
    else
      loop(n - 1, acc2, acc1 + acc2)

  loop(n, 1, 1)
}

리스트 연산에서 꼬리 재귀 사용 예시

리스트 길이 구하기

def lengthTailRecursive[A](ls: List[A]): Int = {
  @tailrec
  def lengthR(result: Int, curList: List[A]): Int = curList match {
    case Nil => result
    case _ :: tail => lengthR(result + 1, tail)
  }
  lengthR(0, ls)
}

리스트 뒤집기

def reverseTailRecursive[A](ls: List[A]): List[A] = {
  @tailrec
  def reverseR(result: List[A], curList: List[A]): List[A] = curList match {
    case Nil        => result
    case h :: tail  => reverseR(h :: result, tail)
  }
  reverseR(Nil, ls)
}

리스트에서 중복된 요소 제거

여기서는 리스트에서 연속된 중복 문자를 하나만 남기고 제거합니다.

// 예제:
// >> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// >> List('a, 'b, 'c, 'a, 'd, 'e)

def compressTailRecursive[A](ls: List[A]): List[A] = {
  @tailrec
  def compressR(result: List[A], curList: List[A]): List[A] = curList match {
    case h :: tail  => compressR(h :: result, tail.dropWhile(_ == h))
    case Nil        => result.reverse
  }
  compressR(Nil, ls)
}