9 재귀 - Recursion

불변성 때문에 Elixir(그리고 함수형 언어)에서 루프는 기존의 절차적 언어와는 다른 방식으로 작성합니다. 예를들어, 절차적 언어에서는 이런 식으로 작성됩니다:

Due to immutability, loops in Elixir (and in functional programming languages) are written differently from conventional imperative languages. For example, in an imperative language, one would write:

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

위의 예제는 배열과 보조 변수 i를 변화시키고 있습니다. Elixir에서는 저렇게 할 수 없습니다. 대신 함수형 언어는 재귀에 의존합니다: 함수는 재귀적으로 호출되어 정지 조건이 될 때까지 계속 작동합니다. 임의의 횟수만큼 문자를 출력하는 다음예를 살펴 봅시다:

In the example above, we are mutating the array and the helper variable i. That's not possible in Elixir. Instead, functional languages rely on recursion: a function is called recursively until a condition is reached that stops the recursive action from continuing. Consider the example below that prints a string an arbitrary amount of times:

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와 유사하게 함수는 여러 절을 가질 수 있습니다. 함수에 전달된 인자가 절의 인자패턴과 일치하고 가드(guard)가 true 로 평가(evaluates)되는 특정 1개의 절이 실행됩니다.

Similar to case, a function may have many clauses. A particular clause is executed when the arguments passed to the function match the clause's argument patterns and its guard evaluates to true.

위 print_multiple_times/2 가 처음 호출 될 때 인자 n 은 3 이 되고 있습니다.

Above when print_multiple_times/2 is initially called, the argument n is equal to 3.

첫 번째 절은 n 이 1 과 같거나 작을 때 사용할 수있는 가드(guard)를 가지고 있습니다. 때문에 Elixir는 다음 절의 정의로 이동합니다.

The first clause has a guard which says use this definition if and only if n is less than or equal to 1. Since this is not the case, Elixir proceeds to the next clause's definition.

두 번째 정의는 패턴과 일치하고 가드(guard)도 없기 때문에 실행됩니다. 먼저 msg 를 출력한 다음 두 번째 인자로 n - 1 (2)을 전달하여 호출합니다. 그러면 msg 가 출력되고 다시 print_multiple_times/2가 호출됩니다. 이 때 두 번째 인자는 1 이됩니다.

The second definition matches the pattern and has no guard so it will be executed. It first prints our msg and then calls itself passing n - 1 (2) as the second argument. Our msg is printed and print_multiple_times/2 is called again this time with the second argument set to 1.

n 이 1이기 때문에, print_multiple_times/2의 첫 번째 정의의 가드(guard)가 참으로 평가되어 이를 실행합니다. msg 가 출력되고 더이상 실행할 것이 없게됩니다.

Because n is now set to 1, the guard to our first definition of print_multiple_times/2 evaluates to true, and we execute this particular definition. The msg is printed, and there is nothing left to execute.

두번째 인자가 어떤값이던지 첫번째 정의("베이스 케이스"라고 합니다)를 호출(trigger)하던지 두번째 정의를 호출하는(trigger) print_multuple_times/2를 정의했습니다.

We defined print_multiple_times/2 so that no matter what number is passed as the second argument it either triggers our first definition (known as a "base case") or it triggers our second definition which will ensure that we get exactly 1 step closer to our base case.

리스트에있는 숫자의 합을 구할 때 재귀의 힘을 어떻게 사용하는지를 살펴 봅시다:

Let's now see how we can use the power of recursion to sum a list of numbers:

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

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

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

We invoke sum_list with a list [1,2,3] and the initial value 0 as arguments. We will try each clause until we find one that matches according to the pattern matching rules. In this case, the list [1,2,3] matches against [head|tail] which assigns head = 1 and tail = [2,3] while accumulator is set to 0.

그런다음 리스트의 head값을 누적변수에 head + accumulator 더한다음 리스트의 tail을 첫번째 인자로로 전달하는 sum_list를 재귀적으로 호출합니다. 리스트의 나머지는 전체 리스트가 비어질때까지 [head|tail]에 일치시키며 다음과 같이 계속됩니다:

Then, we add the head of the list to the accumulator head + accumulator and call sum_list again, recursively, passing the tail of the list as its first argument. The tail will once again match [head|tail] until the list is empty, as seen below:

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

리스트가 비어 있으면, 마지막 절에 매치되어 최종 결과 6 이 리턴됩니다.

When the list is empty, it will match the final clause which returns the final result of 6.

리스트를 취하고 하나의 값으로 "줄여 나간다 (reducing)"라는 과정은 "reduce" 알고리즘이라고하고 함수형 프로그래밍의 중심을 이루고 있습니다.

The process of taking a list and "reducing" it down to one value is known as a "reduce" algorithm and is central to functional programming.

만약 리스트의 모든 값을 두배로하고 싶다면 어떻게 해야할까요?

What if we instead want to double all of the values in our list?

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]

모든 요소를 2배로 하고 새로운 리스트를 리턴하기 위해 재귀를 사용했습니다. 이렇게 리스트를 취하고 "mapping" 하는 기법은 "map" 알고리즘이라고합니다.

Here we have used recursion to traverse a list doubling each element and returning a new list. The process of taking a list and "mapping" over it is known as a "map" algorithm.

재귀와 꼬리(tail) 호출 최적화는 Elixir의 중요한 부분으로 루프를 만드는 데 자주 이용되고 있습니다. 그러나 Elixir로 프로그래밍 할 때 위에서 그랬던 것처럼 리스트를 조작할때 재귀를 사용할 일은 거의 없을 것입니다.

Recursion and tail call optimization are an important part of Elixir and are commonly used to create loops. However, when programming Elixir you will rarely use recursion as above to manipulate lists.

다음 장에서 배울 Enum module은 이미 리스트을 다루는데 여러가지 편리한것들을 제공합니다. 위 예는 다음과 같이 작성될수 있습니다:

The Enum module, which we are going to study in the next chapter, already provides many conveniences for working with lists. For instance, the examples above could be written as:

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]

또는 캡쳐(capture) 문법을 사용하면:

Or, using the capture syntax:

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

그래서 Enumerable와 Stream에 대해 좀 더 자세히 살펴 보겠습니다.

So let's take a deeper look at Enumerables and Streams.