재귀 에서

재귀 소개

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

_재귀 함수_에는 적어도 하나의 _기저 사례_와 적어도 하나의 _재귀 사례_가 있어야 해요.

기저 사례는 함수를 다시 호출하지 않고 값을 반환해요. 재귀 사례는 입력을 바꿔 가면서 함수를 다시 호출해서, 언젠가는 기저 사례와 일치하게 만들어요.

다음은 배열의 원소 개수를 세는 예제예요.

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

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

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

목록에서 주어진 값 x가 몇 번 나타나는지 세는 함수에는 두 개의 _재귀 사례_가 있어요.

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

실제로는 목록이나 다른 열거 가능한 자료 구조를 순회할 때 내장 함수인 map과 reduce를 사용하거나, [.[] | select(...)]처럼 스트림을 사용하는 경우가 가장 많아요. 내부적으로는 일부 내장 함수가 재귀를 사용해 구현되어 있어요.

무한 재귀

재귀 함수를 잘못 구현하면 결과를 영영 반환하지 못할 수도 있어요. 함수가 호출될 때마다 VM이 결과를 돌려줄 위치에 대한 참조가 메모리, 즉 콜 스택에 저장되기 때문에 문제가 될 수 있어요. 재귀 함수가 자기 자신을 무한히 호출하면 메모리가 부족해져서, VM이 스택 오버플로 오류로 중단될 수 있어요.

이런 무한 재귀 문제는 다음과 같은 경우에 발생해요:

• 기저 사례를 구현하는 것을 잊는 경우
• 기저 사례를 첫 번째 절로 정의하지 않는 경우
• 재귀 호출을 할 때 인자를 제대로 수정하지 않아서 기저 사례에 도달하지 못하는 경우

꼬리 호출 최적화

위키백과에 설명된 대로:

꼬리 호출은 프로시저의 마지막 동작으로 수행되는 서브루틴 호출이에요. 꼬리 호출의 대상이 같은 서브루틴이면, 그 서브루틴은 꼬리 재귀적이라고 해요.

위에서 구현한 fibonacci를 한번 살펴봐요. 재귀 사례에서는 자기 자신을 두 번 호출해요. 함수가 수행해야 하는 마지막 동작은 덧셈이에요. 마지막 동작이 자기 자신을 호출하는 것이 아니므로, 이 함수는 재귀적이지만 꼬리 재귀적이지는 않아요.

일부 언어는 _꼬리 호출 최적화_를 구현해서, 꼬리 호출이 콜 스택에 새 프레임을 추가하지 않고 현재 스택 프레임을 재사용할 수 있어요. 이렇게 하면 무서운 스택 오버플로를 막을 수 있을 뿐 아니라 성능상 이점도 얻을 수 있어요.

jq는 꼬리 호출 최적화를 구현하고 있지만, 인자가 0개인 함수에만 적용돼요. 이를 활용하는 방법은 어떤 상태를 입력으로 받는 "내부" 함수를 정의하는 거예요. 이 함수는 인자가 0개여야 해요. 내부 함수는 필요에 따라 상태를 수정하고, 새로운 상태를 꼬리 재귀 호출에 넘겨줄 수 있어요. 바깥 함수는 초기 상태를 만들어서 내부 함수에 넘겨주고, 이렇게 재귀가 시작돼요.

꼬리 재귀적인 fibonacci 함수는 지금까지 계산한 수열을 상태의 일부로 유지하면서 구현할 수 있어요.

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55