재귀 함수: rec 키워드

rec 키워드(keyword) 재귀 함수를 let 정의하기 위해 키워드(keyword) 함께 사용됩니다.

구문

// 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
...

설명

자신을 호출하는 함수인 재귀 함수는 키워드(keyword) 사용하여 F# 언어로 rec 명시적으로 식별됩니다. rec 키워드(keyword) 본문에서 바인딩의 let 이름을 사용할 수 있도록 합니다.

다음 예제에서는 수학 정의를 사용하여 n^번째 피보나치 숫자를 계산하는 재귀 함수를 보여 줍니다.

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

메서드는 정의된 형식 내에서 암시적으로 재귀적이므로 키워드(keyword) 추가할 rec 필요가 없습니다. 예시:

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

let 하지만 클래스 내의 바인딩은 암시적으로 재귀적이지 않습니다. 모든 let바인딩된 함수에는 키워드(keyword) 필요합니다 rec .

비상 재귀

일부 재귀 함수의 경우 좀 더 "순수" 정의를 비상 재귀 함수로 리팩터링해야 합니다. 이렇게 하면 불필요한 재계산을 방지할 수 있습니다. 예를 들어 이전 피보나치 숫자 생성기는 다음과 같이 다시 작성할 수 있습니다.

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

피보나치 숫자를 생성하는 것은 수학적으로 순수하지만 실제로 비효율적인 "순진한" 알고리즘의 좋은 예입니다. 보다 복잡한 구현이지만, 재귀적으로 다시 정의되는 동안 F#에서 여러 측면을 통해 효율적으로 기본.

• idiomatic F# 패턴인 재귀 내부 함수입니다 loop.
• 누적된 값을 재귀 호출에 전달하는 두 개의 누적기 매개 변수입니다.
• 특정 누적기를 반환할 값에 n 대한 검사.

이 예제를 루프로 반복적으로 작성한 경우 코드는 특정 조건이 충족될 때까지 숫자를 누적하는 두 개의 서로 다른 값과 유사하게 표시됩니다.

이것이 비상 재귀적인 이유는 재귀 호출이 호출 스택에 값을 저장할 필요가 없기 때문입니다. 계산되는 모든 중간 값은 내부 함수에 대한 입력을 통해 누적됩니다. 또한 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)

는 두 개의 비상 재귀 호출에 대한 컴파일러 경고를 트리거합니다.

상호 재귀 함수

경우에 따라 함수는 상호 재귀적입니다. 즉, 호출이 원을 형성합니다. 즉, 한 함수가 다른 함수를 호출하여 첫 번째 함수를 호출하고 그 사이에는 호출 수가 없습니다. 이러한 함수는 키워드(keyword) 사용하여 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)

재귀 값

재귀적으로 let바인딩된 값을 정의할 수도 있습니다. 이 작업은 로깅을 위해 수행되는 경우도 있습니다. F# 5 및 함수를 nameof 사용하면 다음을 수행할 수 있습니다.

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

참고 항목

• 함수