재귀 에서

재귀 소개

어떤 것이 스스로를 이용해 정의되는 것을 재귀라고 해요. F#에서 재귀는 주로 재귀 함수에서 볼 수 있는데, 재귀 함수란 자기 자신을 호출하는 함수예요.

재귀 함수에는 _기본 사례_가 최소한 하나, _재귀 사례_가 최소한 하나 있어야 해요. _기본 사례_는 함수를 다시 호출하지 않고 값을 반환해요. _재귀 사례_는 함수를 다시 호출하는데, 언젠가는 기본 사례와 일치하도록 입력을 바꿔서 호출해요.

재귀 함수는 일반 함수처럼 정의하지만, rec 한정자를 붙여요. 이 한정자가 없으면 함수는 자기 자신을 호출할 수 없고, 호출을 시도하면 컴파일 오류가 발생해요. 그래서 재귀는 명시적으로 선택해야 해요.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

배열은 재귀로 처리하는 경우가 많아요. 예를 들어, 재귀를 이용해 배열의 길이를 구하는 방법은 다음과 같아요.

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

내장 함수 중 상당수는 재귀로 정의되어 있어요.

재귀 함수의 한 가지 문제는 (재귀) 함수를 호출할 때마다 스택에 할당이 생겨서 스택이 커진다는 점이에요. 스택의 메모리는 한정되어 있기 때문에, 재귀 호출을 많이 사용하는 함수는 StackOverflowException을 발생시킬 수 있어요. 재귀 호출이 몇 번일 때 이런 현상이 나타나는지는 스택에 남은 메모리, 함수 호출 하나가 스택에서 차지하는 데이터의 양 등 여러 요인에 따라 달라요.

재귀 함수가 스택을 넘치게 하지 않도록 하는 가장 좋은 방법은 함수를 꼬리 재귀 함수로 작성하는 거예요. 함수가 꼬리 재귀이면, 컴파일러는 재귀 함수를 호출할 때마다 스택에 추가로 할당이 생기지 않도록 결과를 최적화할 수 있어요. 꼬리 재귀 함수의 유일한 규칙은 재귀 호출의 결과가 함수에서 곧바로 반환되어야 한다는 것으로, 재귀 호출의 결과를 추가로 처리하는 코드가 있어서는 안 돼요. 가장 흔한 방법은 누산기 인자를 하나 더 받는 도우미 함수를 만드는 것인데, 이 인자는 재귀 호출마다 갱신되고 재귀가 끝나면 반환돼요. 이 페이지에서는 컴파일러가 꼬리 재귀 함수를 처리하는 방법을 아주 자세히 다뤄요.

다음은 배열 길이 함수를 꼬리 재귀로 작성한 버전이에요.

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

재귀 도우미를 중첩 함수로 정의하는 것도 흔한데, 이렇게 하면 호출하는 쪽에서 함수의 재귀적인 성격이 보이지 않아요.

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F#은 판별 공용체 형식을 통한 재귀 형식을 지원해요. 재귀 판별 공용체 형식은 사례 중 하나 이상이 자신의 데이터에서 판별 공용체 형식 자체를 가리켜요. 재귀 함수와 마찬가지로 재귀 형식에도 기본 사례가 있어야 해요. 재귀 함수와 달리, 재귀 형식은 rec 키워드를 쓰지 않아요.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

다음은 위의 재귀 형식을 다루는 (꼬리 재귀가 아닌) 함수예요.

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1