재귀 에서

재귀 소개

재귀 함수는 자기 자신을 호출하는 함수예요.

재귀 함수에는 _기저 사례_가 최소한 하나, _재귀 사례_가 최소한 하나 있어야 해요.

_기저 사례_는 함수를 다시 호출하지 않고 값을 반환해요. _재귀 사례_는 입력값을 바꾸면서 함수를 다시 호출하고, 그러다 보면 언젠가 기저 사례와 맞아떨어져요.

아주 흔하게는, 각 사례를 각자의 함수 절에 따로 작성해요.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

재귀 함수는 기저 사례를 여러 개 가질 수도 있고, 재귀 사례를 여러 개 가질 수도 있어요. 예를 들어 피보나치 수열은 기저 사례가 두 개인 재귀 수열이에요:

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

배열에서 주어진 값 x가 몇 번 나타나는지 세는 함수에는 재귀 사례가 두 개 있어요:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

재귀로 구현하는 루프

불변성 때문에 Elixir의 루프는 명령형 언어와 다르게 작성해요. 예를 들어, 루프는 흔히 이렇게 생겼어요:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

함수형 언어에서는 i++를 호출해서 i를 변경할 수 없어요. 그래서 루프는 재귀로 구현해야 해요.

Elixir에서 for문에 해당하는 것은 이렇게 생겼어요:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

실제로는 배열이나 다른 열거 가능한 자료 구조를 순회할 때 Enum 모듈을 가장 많이 사용해요. 내부적으로 Enum 모듈의 함수들은 재귀로 구현되어 있어요.

무한 실행

재귀 함수를 잘못 구현하면 결과를 영영 반환하지 못할 수도 있어요. 함수를 호출할 때마다 VM이 결과를 돌려줘야 할 위치(호출 스택)에 참조가 메모리에 저장되기 때문에 문제가 될 수 있어요. 재귀 함수가 자기 자신을 무한히 호출하면 메모리가 부족해져서 VM이 멈출 수도 있어요(스택 오버플로 오류). Elixir가 실행되는 Erlang VM은 재귀와 안정성을 위해 특별히 최적화되어 있어서, 무한 재귀 오류가 드러나거나 충돌이 일어나기까지 오랜 시간이 걸릴 수 있어요.

이런 무한 실행 문제는 다음과 같은 이유로 생겨요:

• 기저 사례를 구현하는 것을 잊었을 때.
• 기저 사례를 첫 번째 절로 정의하지 않았을 때.
• 재귀 호출을 할 때 인자를 제대로 바꾸지 않아서 기저 사례에 결코 도달하지 못할 때.