꼬리 호출 최적화 에서

꼬리 호출 최적화 소개

함수가 호출될 때마다 인자와 함수의 지역 변수를 저장하기 위해 메모리에 새로운 스택 프레임이 만들어지고, 이 스택 프레임은 함수가 반환될 때 해제돼요. Gleam은 루프 문법 대신 재귀 함수 호출을 사용하기 때문에 이런 스택 프레임이 많은 메모리를 차지할 수 있어요.

이 문제를 피하기 위해 Gleam은 꼬리 호출 최적화를 지원해요. 함수가 마지막으로 하는 일이 함수 호출이라면, 이 최적화를 통해 컴파일러가 현재 함수의 스택 프레임을 재사용할 수 있어요. 즉, 함수가 자기 자신을 무한히 호출해도 추가 메모리를 전혀 사용하지 않아요.

최적화되지 않은 재귀 함수는 누산기를 사용하면 꼬리 호출 최적화된 함수로 다시 쓸 수 있는 경우가 많아요.

누산기는 데이터와 함께 전달되는 변수예요. 기저 사례에 도달할 때까지 함수 실행의 현재 상태를 전달하는 데 사용해요.

누산기는 함수를 사용하는 사람이 아니라 함수를 작성한 사람이 초기화해야 해요. 그러려면 함수 두 개를 선언해요. 필요한 데이터만 인자로 받아 누산기를 초기화하는 공개 함수와, 누산기도 함께 받는 비공개 함수예요.

// Count the length of a list without tail call optimisation
pub fn count(list: List(String)) -> Int {
  case list {
    [] -> 0
    [_, ..rest] -> {
      let amount = count(rest) // Non-tail recursive call
      amount + 1
    }
  }
}

// Count the length of a list with tail call optimisation
pub fn count(list: List(String)) -> Int {
  count_elements(list, 0)
}

fn count_elements(list: List(String), accumulator: Int) -> Int {
  case list {
    [] -> accumulator
    [_, ..rest] -> {
      let accumulator = accumulator + 1
      count_elements(rest, accumulator) // Tail recursive call
    }
  }
}