재귀 함수: rec 키워드

재귀 함수: rec 키워드 (Let Recursion)

rec 키워드를 let 키워드와 함께 쓰면 재귀 함수를 정의할 수 있어요. 함수가 자기 자신을 다시 호출해야 할 때, F#에서는 그 의도를 rec 키워드로 명확하게 드러내 주는 방식이에요.

출처

원문: Recursive Functions: The rec Keyword - F# | Microsoft Learn

본문

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

구문 (Syntax)

// 재귀 함수:
let rec function-name parameter-list =
    function-body

// 상호 재귀 함수:
let rec function1-name parameter-list =
    function1-body

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

설명 (Remarks)

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

다음 예시는 수학적 정의 그대로 n번째 피보나치(Fibonacci) 수를 계산하는 재귀 함수예요.

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

참고

실전에서 위와 같은 코드는 이상적이지 않아요. 이미 계산된 값을 불필요하게 다시 계산하거든요. 이는 이 함수가 꼬리 재귀(tail recursive)가 아니기 때문인데, 이에 대해서는 이 글에서 자세히 다룰게요.

메서드(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 값을 확인해서 특정 누산기를 반환해요.

이 예시를 while 반복문으로 작성한다면, 두 개의 값을 특정 조건이 될 때까지 누적해 나가는 비슷한 모양이 될 거예요.

이 구현이 꼬리 재귀인 이유는, 재귀 호출이 호출 스택에 어떤 값을 저장할 필요가 없기 때문이에요. 계산되는 모든 중간 값은 내부 함수의 입력을 통해 누적되거든요. 덕분에 F# 컴파일러가 while 반복문을 쓴 것만큼 빠르게 코드를 최적화할 수도 있어요.

위 예시처럼 내부 함수와 외부 함수를 사용해서 무언가를 재귀적으로 처리하는 F# 코드는 흔해요. 내부 함수는 꼬리 재귀를 쓰고, 외부 함수는 호출자에게 더 나은 인터페이스를 제공하죠.

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

예를 들어 첫 번째 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

더 알아보기

Functions