재귀 함수: rec 키워드

F#에서 함수가 자기 자신을 호출하는 재귀 함수임을 명시할 때는 rec 키워드를 사용해요. 이 글에서는 재귀 함수를 정의하는 문법과 성능을 높이는 꼬리 재귀(tail recursion) 기법, 그리고 서로를 호출하는 상호 재귀 함수까지 정리해 볼게요.

출처: https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/functions/recursive-functions-the-rec-keyword

본문

rec 키워드는 let 키워드와 함께 사용해 재귀 함수를 정의할 때 쓰여요.

문법 (Syntax)

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

설명 (Remarks)

자기 자신을 호출하는 함수인 재귀 함수는 F# 언어에서 rec 키워드로 명시적으로 구분돼요. rec 키워드는 let 바인딩의 이름이 그 함수 본문 안에서도 사용될 수 있게 해 줘요.

다음 예제는 수학적 정의를 그대로 사용해 n번째 피보나치 수를 계산하는 재귀 함수예요.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

참고 — 실무에서는 위 예제처럼 작성하지 않는 게 좋아요. 이미 계산된 값을 불필요하게 다시 계산하기 때문이에요. 이 함수는 꼬리 재귀가 아니라서 그런데, 이에 대해서는 이 글 뒤쪽에서 더 자세히 설명할게요.

메서드(method)는 자신이 정의된 타입 안에서 암묵적으로 재귀적이라 rec 키워드를 붙일 필요가 없어요. 예를 들면 다음과 같죠.

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

하지만 클래스 안의 let 바인딩은 암묵적으로 재귀적이지 않아요. let으로 바인딩된 함수는 모두 rec 키워드가 필요해요.

꼬리 재귀 (Tail recursion)

일부 재귀 함수는 더 "순수한" 정의를 꼬리 재귀 형태로 리팩터링해야 할 때가 있어요. 그러면 불필요한 재계산을 막을 수 있어요. 예를 들어 앞서 본 피보나치 수 생성기는 다음과 같이 다시 작성할 수 있어요.

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

피보나치 수를 만드는 건 수학적으로는 순수하지만 실제로는 비효율적인 "순진한(naive)" 알고리즘의 전형적인 예시예요. 위 구현은 좀 더 복잡하지만, F#에서 효율적으로 동작하게 하는 몇 가지 요소가 있어요. 그래도 재귀로 정의된 형태는 그대로 유지돼요.

재귀적인 내부 함수로 이름을 loop라고 지었는데, 이건 F#에서 흔히 쓰는 관용적 패턴이에요.
누산기(accumulator) 역할을 하는 매개변수 두 개가 있어서, 누적된 값을 재귀 호출로 전달해요.
n 값을 확인해서 특정 누산기를 반환하는 분기가 있어요.

이 예제를 반복문(loop)으로 작성한다면, 값 두 개를 특정 조건이 될 때까지 누적해 가는 비슷한 코드가 될 거예요.

이 함수가 꼬리 재귀인 이유는 재귀 호출이 호출 스택(call stack)에 아무 값도 저장할 필요가 없기 때문이에요. 계산되는 중간 값들은 전부 내부 함수의 입력으로 누적되죠. 덕분에 F# 컴파일러가 코드를 while 반복문을 쓴 것만큼 빠르게 최적화할 수 있어요.

앞의 예제처럼 F# 코드에서 내부/외부 함수로 재귀적인 처리를 작성하는 건 흔한 일이에요. 내부 함수는 꼬리 재귀를 쓰고, 외부 함수는 호출하는 쪽에 더 나은 인터페이스를 제공하는 구조죠.

F# 8.0부터는 TailCall 특성을 사용해서 꼬리 재귀 함수를 정의하겠다는 의도를 컴파일러에 명시할 수 있어요. 그러면 함수에 꼬리 재귀가 아닌 호출이 있으면 컴파일러가 경고를 띄워 줘요. 이 특성은 메서드와 모듈 수준 함수에 사용할 수 있어요.

예를 들어 첫 번째 fib 정의에 적용하면:

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

꼬리 재귀가 아닌 두 번의 호출에 대해 컴파일러 경고가 발생해요.

상호 재귀 함수 (Mutually Recursive Functions)

때로는 함수들이 서로를 호출하는 상호 재귀 관계에 있을 수 있어요. 즉 호출이 원을 이루는 형태로, 어떤 함수가 다른 함수를 호출하고 그 함수가 다시 첫 함수를 호출하며 그 사이에 호출이 몇 번이고 끼어들어 있는 거죠. 이런 함수들은 and 키워드로 서로를 연결해서 하나의 let 바인딩 안에 함께 정의해야 해요.

다음 예제는 서로 재귀하는 함수 두 개를 보여 줘요.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

재귀 값 (Recursive values)

let으로 바인딩된 값을 재귀적으로 정의할 수도 있어요. 주로 로깅 용도로 쓰이곤 해요. F# 5 이상에서 nameof 함수를 쓰면 다음과 같이 할 수 있어요.

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

더 알아보기 (Learn more)

Functions