Elixir Tutorial 시리즈입니다. 거의 대부분은 튜토리얼의 한글 번역에 가깝습니다만, 생략되거나 추가로 주석을 달거나 하는 부분이 많습니다. 원문은 최하단의 링크를 참고하세요.

Elixir – 09: Recursion

Loops through recursion

Elixir의 루프는 불변성 때문에 (다른 함수형 언어에서도 그렇겠지만) 일반적인 절차형 언어와는 많이 다릅니다. 예를 들어 JavaScript와 같은 언어에서는 다음과 같이 작성할 수 있습니다.

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

이 예제에서는 i라는 변수와 배열이 모두 변경되고 있습니다. 그러나 Elixir에서는 이러한 변경이 가능하지 않습니다. 때문에 함수형 언어들은 재귀에 의존합니다. 재귀에서는 어떠한 데이터도 변경되지 않는 다는 점을 기억하세요. 주어진 임의의 횟수만큼 문자열을 반복해서 출력하는 예제를 한번 보시죠.

defmodule Recursion do
  def print_multiple_times(msg, n) when n <= 1 do
    IO.puts msg
  end

  def print_multiple_times(msg, n) do
    IO.puts msg
    print_multiple_times(msg, n - 1)
  end
end

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

case와 마찬가지로, 함수 역시 많은 함수절을 가질 수 있습니다. 몇몇 함수절들은 패턴이 매칭되고, 가드의 조건이 true일 경우에만 실행됩니다.

print_multiple_times/2가 처음 호출될 때에는 n이 3입니다.

첫번째 함수절은 “n이 1 이하일 때에만 사용해.”라는 가드를 가지고 있습니다. 그러므로 이번 경우에서는 사용되지 않으며, Elixir는 다음 함수절 정의를 찾습니다.

두번째 함수절은 함수의 시그니처가 매칭되고, 가드가 존재하지 않으므로 실행될 겁니다. 우선 첫번째 msg를 실행하고, 자기 자신에 대해서 n - 1(2)를 두번째 인수로 넘겨줍니다.

다시 msg가 출력되며 print_multiple_times/2가 호출되며, 이번에는 두번째 인수가 1로 넘겨집니다.
n이 1이 되었기 때문에, print_multiple_times/2의 첫번째 함수절의 가드가 참이 되어 이 정의를 실행할 수 있습니다. 이제 msg가 출력되고 모든 실행이 종료됩니다.

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이 할당됩니다.

그리고나서 남은 tail과 head + accumulator 한 값을 다시 sum_list 호출에 사용합니다. 이는 리스트가 빌 때까지 반복됩니다. -리스트가 비게 되면 [head|tail]되지 않았다는 점을 떠올리세요-

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

리스트가 비면, 이는 마지막 함수절과 매칭하여 모두를 합산한 값인 6을 반환합니다.

이런식으로 리스트를 받아서 하나의 값으로 줄여나가는 방식은 _리듀스 알고리즘_이라는 이름으로 널리 알려져있으며, 이는 함수형 프로그래밍의 핵심입니다.

만약 리스트에 있는 모든 값을 2배로 증가시키고 싶다면 어떻게 해야할까요?

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

  def double_each([]) do
    []
  end
end

iex math.exs

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

이 예제에서는 리스트를 순회하기 위해서 재귀를 사용했으며, 각 원소들을 두배로 만들어서 새 리스트에 집어넣었습니다. 이는 리스트의 각 원들을 사상하는 _맵 알고리즘_으로 널리 알려져 있는 것입니다.

재귀와 꼬리 호출 최적화는 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]

Reference

Array

Elixir – 09: Recursion