再帰関数: rec キーワード

再帰関数: rec キーワード Recursive Functions: The rec Keyword

元ネタ http://msdn.microsoft.com/ja-jp/library/dd233232.aspx

rec キーワードは、再帰関数を定義するときに let キーワードと一緒に使用します。

n 番目のフィボナッチ数を計算する再帰関数を次のコードに示します。

F#

let rec fib n =
   if n <= 2 then 1
   else fib (n - 1) + fib (n - 2)

「メソッドは型の中では暗黙的に再帰的になります。rec キーワードを追加する必要はありません。 クラス内の Let 束縛は、暗黙的に再帰的ではありません。」ということなので、let する時だけ rec が必要になる。

C# の場合は、そのまま。

C#

public int fib(int n)
{
    if (n <= 2)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

相互再帰関数

このような関数は、and を使用して 1 つの let 束縛で一緒に定義し、相互にリンクする必要があります。

F#

let rec Even x =
   if x = 0 then true
   else Odd (x - 1)
and Odd x =
   if x = 1 then true
   else Even (x - 1)

C# の場合は、そのまま。

F#

public bool Even(int x)
{
    if (x == 0)
        return true;
    else 
        return Odd(x - 1);
}
public bool Odd(int x)
{
    if (x == 1)
        return true;
    else
        return Even(x - 1);
}