재귀

재귀 (Recursion)

Elixir에는 for나 while 같은 반복(loop) 구문이 없어요. 대신 재귀와 고차 함수를 활용해서 컬렉션을 다루죠. 이번 장에서는 그중 재귀를 자세히 살펴볼게요.

출처: Elixir 공식 가이드

본문

Elixir에는 반복 구문이 없어요. 대신 재귀와 컬렉션 처리용 고차 함수를 활용하죠. 이번 장에서는 전자인 재귀를 살펴볼게요.

재귀로 반복하기 (Loops through recursion)

불변성(immutability) 때문에 Elixir(그리고 다른 함수형 언어들)의 반복은 명령형 언어와 다르게 작성돼요. 예를 들어 C 같은 명령형 언어에서는 이렇게 쓰죠.

for(i = 0; i < sizeof(array); i++) {
  array[i] = array[i] * 2;
}

위 예시에서는 배열도, 변수 i도 계속 변형(mutate)하고 있어요. 하지만 Elixir의 데이터 구조는 불변이라서, 함수형 언어는 재귀에 의존해요. 어떤 조건이 재귀 동작을 멈출 때까지 함수를 재귀적으로 호출하는 거예요. 이 과정에서 데이터는 전혀 변형되지 않아요. 문자열을 원하는 횟수만큼 출력하는 예시를 볼까요.

defmodule Recursion do
  def print_multiple_times(msg, n) when n > 0 do
    IO.puts(msg)
    print_multiple_times(msg, n - 1)
  end

  def print_multiple_times(_msg, 0) do
    :ok
  end
end

Recursion.print_multiple_times("Hello!", 3)
# Hello!
# Hello!
# Hello!
:ok

case와 비슷하게, 함수는 여러 개의 절(clause)을 가질 수 있어요. 함수에 전달된 인자가 어떤 절의 인자 패턴과 일치하고 그 절의 가드(guard)가 true로 평가되면 그 절이 실행돼요.

위 예시에서 print_multiple_times/2가 처음 호출될 때 n은 3이에요.

첫 번째 절은 "n이 0보다 클 때만 이 정의를 쓰라"는 가드를 달고 있어요. 지금은 그 조건이 성립하므로 메시지를 출력하고 n - 1(즉 2)을 두 번째 인자로 넘기면서 자기 자신을 다시 호출해요.

그러면 같은 함수가 다시 첫 번째 절부터 실행돼요. 두 번째 인자 n이 여전히 0보다 크므로 메시지를 출력하고, 이번에는 두 번째 인자를 1로 해서 다시 호출해요. 그리고 마지막으로 한 번 더 메시지를 출력한 뒤 print_multiple_times("Hello!", 0)을 호출하며 다시 처음부터 시작하죠.

두 번째 인자가 0이 되면 가드 n > 0이 false로 평가되므로 첫 번째 절은 실행되지 않아요. Elixir는 그다음 함수 절로 넘어가는데, 이 절은 정확히 n이 0인 경우에만 매치돼요. 종료 절(termination clause) 이라고도 불리는 이 절은 메시지 인자를 _msg 변수에 할당해 무시하고, :ok라는 원자를 반환해요.

마지막으로, 어떤 절과도 매치되지 않는 인자를 넘기면 FunctionClauseError가 발생해요.

iex> Recursion.print_multiple_times("Hello!", -1)
** (FunctionClauseError) no function clause matching in Recursion.print_multiple_times/2

    The following arguments were given to Recursion.print_multiple_times/2:

        # 1
        "Hello!"

        # 2
        -1

    iex:1: Recursion.print_multiple_times/2

reduce와 map 알고리즘 (Reduce and map algorithms)

이제 재귀의 힘으로 숫자 리스트의 합을 구하는 예시를 볼게요.

defmodule Math do
  def sum_list([head | tail], accumulator) do
    sum_list(tail, head + accumulator)
  end

  def sum_list([], accumulator) do
    accumulator
  end
end

IO.puts Math.sum_list([1, 2, 3], 0) #=> 6

sum_list를 리스트 [1, 2, 3]과 초기값 0을 인자로 호출해요. 패턴 매칭 규칙에 따라 매치되는 절을 찾을 때까지 각 절을 시도하죠. 여기서 [1, 2, 3]은 [head | tail]에 매치되고, head에 1이, tail에 [2, 3]이 바인딩되며, accumulator는 0으로 설정돼요.

그다음 리스트의 head를 accumulator에 더한 값(head + accumulator)에서, tail을 첫 번째 인자로 넘기며 sum_list를 재귀적으로 다시 호출해요. tail은 리스트가 빌 때까지 계속 [head | tail]에 매치되죠. 아래처럼요.

sum_list([1, 2, 3], 0)
sum_list([2, 3], 1)
sum_list([3], 3)
sum_list([], 6)

리스트가 비면 마지막 절에 매치되어 최종 결과 6을 반환해요.

리스트를 받아 하나의 값으로 줄여나가는 이 과정을 reduce 알고리즘이라고 하고, 함수형 프로그래밍의 핵심이에요.

그럼 리스트의 모든 값을 두 배로 만들고 싶다면 어떻게 할까요?

defmodule Math do
  def double_each([head | tail]) do
    [head * 2 | double_each(tail)]
  end

  def double_each([]) do
    []
  end
end

Math.double_each([1, 2, 3]) #=> [2, 4, 6]

여기서는 재귀로 리스트를 순회하면서 각 원소를 두 배로 만들고 새 리스트를 반환했어요. 리스트를 받아 각 원소에 어떤 변환을 적용하는 이 과정을 map 알고리즘이라고 해요.

재귀와 꼬리 호출 최적화(tail call optimization)는 Elixir의 중요한 부분이고, 반복을 만들 때 흔히 쓰여요. 다만 실제로 Elixir로 프로그래밍할 때 위처럼 재귀로 리스트를 조작하는 일은 거의 없어요.

다음 장에서 볼 Enum 모듈이 이미 리스트 작업을 위한 편의 함수들을 많이 제공하거든요. 사실 위 예시들은 이렇게도 쓸 수 있어요.

iex> Enum.reduce([1, 2, 3], 0, fn x, acc -> x + acc end)
6
iex> Enum.map([1, 2, 3], fn x -> x * 2 end)
[2, 4, 6]

& 캡처 문법을 써서 더 간결하게도 표현할 수 있어요.

iex> Enum.reduce([1, 2, 3], 0, &+/2)
6
iex> Enum.map([1, 2, 3], &(&1 * 2))
[2, 4, 6]

이제 Enumerable을 더 깊이 들여다보고, 그 지연(lazy) 버전인 Stream도 함께 살펴볼게요.

더 알아보기

• Enumerables and Streams (다음 장)
• Enum 모듈 (Elixir 공식 문서)