再帰関数: rec キーワード

rec キーワードは、再帰関数を定義するために let キーワードと共に使用されます。

構文

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

注釈

再帰関数 (自身を呼び出す関数) は、 rec キーワードを使用して F# 言語で明示的に識別されます。 rec キーワードを使用すると、let バインドの名前を本文で使用できるようになります。

次の例は、数学定義を使用して n^番目 のフィボナッチ数を計算する再帰関数を示しています。

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

メソッドは、定義されている型内で暗黙的に再帰的であるため、 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 キーワードが必要です。

末尾再帰

一部の再帰関数では、より "純粋" な定義を 末尾再帰型の定義にリファクタリングする必要があります。 これにより、不要な再計算が防止されます。 たとえば、前のフィボナッチ数ジェネレーターは次のように書き換えることができます。

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# ではいくつかの側面が効率的になりますが、再帰的に定義されたままです。

• loopという名前の再帰的な内部関数。これは慣用的な F# パターンです。
• 累積値を再帰呼び出しに渡す 2 つのアキュムレータ パラメーター。
• 特定のアキュムレータを返す n の値のチェック。

この例がループを使用して繰り返し記述された場合、コードは、特定の条件が満たされるまで、数値を累積する 2 つの異なる値で似ています。

これが末尾再帰である理由は、再帰呼び出しが呼び出し履歴に値を保存する必要がないためです。 計算されるすべての中間値は、内部関数への入力によって累積されます。 これにより、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)

は、2 つの非末尾再帰呼び出しに関するコンパイラ警告をトリガーします。

相互再帰関数

関数が 相互に再帰的な場合があります。つまり、呼び出しは円を形成し、1 つの関数が別の関数を呼び出し、その間に任意の数の呼び出しを行って最初の関数を呼び出します。 このような関数は、and キーワードを使用して 1 つのlet バインドで一緒に定義して、それらをリンクする必要があります。

次の例は、2 つの相互再帰関数を示しています。

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

こちらも参照ください

• 関数