피자 가격 책정

재귀

어떤 것이 자기 자신을 이용해 정의될 수 있는 능력을 재귀라고 해요. F#에서 재귀는 주로 자기 자신을 호출하는 함수인 재귀 함수에서 볼 수 있어요.

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

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

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

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

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