再帰 の

再帰について

あるものがそれ自身を使って定義できる性質を、再帰と呼びます。F#では、再帰は再帰関数で最もよく使われます。再帰関数とは、自分自身を呼び出す関数のことです。

再帰関数には、少なくとも1つの_基底ケース_と、少なくとも1つの_再帰ケース_が必要です。_基底ケース_は、関数を再度呼び出さずに値を返します。_再帰ケース_は、入力を変更しながら関数を再度呼び出し、いずれ基底ケースに一致するようにします。

再帰関数は通常の関数と同じように定義しますが、rec修飾子を付けます。この修飾子がないと、関数は自分自身を呼び出すことが_できず_、呼び出そうとするとコンパイルエラーになります。そのため、再帰を使うには明示的に指定する必要があります。

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

配列は再帰的に処理されることがよくあります。たとえば、再帰を使って配列の長さを計算する方法は次のとおりです。

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

組み込み関数の多くは再帰的に定義されています。

再帰関数の起こりうる問題の1つは、（再帰的な）関数を呼び出すたびにスタック上に割り当てが発生し、スタックが大きくなることです。スタックのメモリ量には限りがあるため、再帰呼び出しを多く使う関数では、StackOverflowExceptionがスローされることがあります。何回の再帰呼び出しでこの現象が起きるかは、スタックで利用できるメモリ量や、関数呼び出し1回あたりがスタック上で占めるデータ量など、いくつもの要因によって変わります。

再帰関数によるスタックのオーバーフローを防ぐ最善の方法は、_末尾再帰_関数として書くことです。関数が末尾再帰になっていると、コンパイラーは出力を最適化し、再帰呼び出しのたびにスタック上へ新たに割り当てが発生しないようにできます。末尾再帰関数の唯一のルールは、再帰呼び出しの結果をそのまま関数から返すことです。再帰呼び出しの結果を処理する追加のコードがあってはなりません。これを実現する最も一般的な方法は、追加のアキュムレーター引数を取るヘルパー関数を作ることです。この引数は再帰呼び出しのたびに更新され、再帰が終わったときに返されます。こちらのページでは、コンパイラーが末尾再帰関数をどのように処理するかが詳しく解説されています。

以下は、配列の長さを求める関数を末尾再帰で書いたものです。

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

再帰的なヘルパーを入れ子の関数として定義するのはよくあることです。こうすると、関数の再帰的な性質を呼び出し元から隠せます。

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F#は判別共用体による再帰型をサポートしています。再帰的な判別共用体では、1つ以上のケースが、そのデータの中で判別共用体自身を参照します。再帰関数と同じく、再帰型にも基底ケースが必要です。再帰関数とは異なり、再帰型ではrecキーワードを使いません。

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

以下は、上記の再帰型を扱う（末尾再帰ではない）関数です。

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1