再帰関数: 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
...

解説

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

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

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

Note

実際には、前のサンプルのようなコードは、既に計算されている値を不必要に再計算しているため、理想的ではありません。 これは、この記事で詳しく説明されている末尾再帰ではないためです。

メソッドは、それが定義されている型内で暗黙的に再帰になるため、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 つの異なる数値を累積していくものになります。

これが末尾再帰であると言えるのは、この再帰呼び出しでは、コール スタックに値を保存する必要がないためです。 計算されるすべての中間値は、内部関数への入力によって累積されます。 こうすれば、while ループのようなものを記述した場合と同様に高速になるよう、F# コンパイラでコードを最適化することもできます。

前の例で示したように、内部および外部関数を使用して何かを再帰的に処理する 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 つの let バインドの中で一緒に定義し、and キーワードを使用してそれらをリンクする必要があります。

次の例は、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

関連項目

• 関数