情報アイランド

「情報を制する者は世界を制す」をモットーに様々な情報を提供することを目指すブログです。現在はプログラミング関連情報が多めですが、投資関連情報も取り扱っていきたいです。

F#入門(9)再帰

※最初はF#とは無関係の、数学を交えた再帰の話です。再帰について理解している人はスルーして問題ないです。

再帰(recursion)とは、あるものの定義の中に、それ自身を含むようなことを言います。

再帰は数学的帰納法と密接な関連があるというか、再帰的構造を含む命題の真正性を証明するための技法が数学的帰納法(より一般的に構造的帰納法、更に発展して相互的帰納法など)です。

そこで、数学的帰納法による証明手順を思い出してみましょう。

★整数n≧iについての命題S(n)を証明したい。

 (ⅰ)基礎(basic case):ある整数iについてS(i)が正しいことを示す。普通はi=0またはi=1であるが、iが小さいところでは幾つかSが成り立たない場合もあるために、もっと大きなiから始めることもある。

 (ⅱ)再帰(recursive case):n≧iと仮定して、「もしS(n)ならばS(n+1)」であることを証明する。ここでiは基礎となる整数である。

これではいささか威力が不十分なのでより一般化した形も書いておきます。

★整数n≧iについての命題S(n)を証明したい(強化ver)。

 (ⅰ)基礎:ある整数j≧iについてS(i), S(i+1), ……, S(j)が正しいことを示す。

 (ⅱ)再帰:n≧jと仮定して、「もしS(i), S(i+1), ……, S(n)ならばS(n+1)」であることを証明する。

このように、複数個の基礎を持たせたり、再帰でその場合より前に証明した場合を好きなだけ利用したりすることで数学的帰納法はより強力なものになります。

では、何故数学的帰納法によって整数に関する再帰的構造を含む命題を証明できるのかというと――それは帰納法の原理として認められている訳ですが――再帰的構造が基礎と再帰の二つの部分を持つからに他なりません。

このことから逆に再帰的構造に必要な要素はもう明らかです。

★整数に関する再帰的構造の定義

 (ⅰ)基礎:ある整数j≧iについてS(i), S(i+1), ……, S(j)の定義。

 (ⅱ)再帰:n≧jで、S(i), S(i+1), ……, S(n)を使ったS(n+1)の定義。

勿論プログラムで再帰的構造を定義する時も上の定義方法に従わねばなりません。

上の要件を満たしていないといつまでも止まらなかったりするプログラムができます(プログラミングの場合はスタックオーバーフローも考慮せねばなりませんが)。

F#で再帰を利用する場合は、letキーワードの後にrecキーワードを付けて関数を定義します。こうすることで関数の定義の中でその関数自身を呼び出すことができるようになります。

例えば、階乗を求める再帰関数は以下のようになります。

let rec factorial (x:bigint) =

    match x with

    | 0I -> 1I

    | x  -> x * factorial (x - 1I)

階乗は

と定義できるので、これをそのままプログラムの形に変換すれば良いのですが、上のプログラムではまだ説明していない型注釈とパターンマッチングを使っています。

直感的に分かると思いますが、match x withxの値によって場合分けし、それぞれの場合で関数が返す値を与えています。

パターンマッチングの最初の場合(3行目)はx=0の場合であり、これは「基礎」の部分です。次の場合(4行目)はx=0以外の場合であり、これは「再帰」の部分です。

また、引数xx:bigintという風に型が指定されています。このようにすると関数の引数としてその型の値しか渡せなくなります。この例では、大数を扱えるようにするため、xの引数としてbigint型を指定してみました。

100!を計算してみると、正しく計算されるのが分かります。

他にも幾つか再帰を使った代表的な関数を定義してみましょう。

多重階乗(k重階乗)は

と定義できるので、下のようなプログラムで計算できます。パターンマッチングの最初の場合(3行目)はx<=0の場合です。このようにwhenキーワードの後に条件を続けます。

let rec multifactorial (k:bigint) (x:bigint) =

    match x with

    | x when x <= 0I -> 1I

    | x -> x * multifactorial k (x - k)

フィボナッチ数は

と定義できるので、下のようなプログラムで計算できます。

let rec fibonacci_number (x:bigint) =

    match x with

    | 0I -> 0I

    | 1I -> 1I

    | x  -> fibonacci_number(x - 2I) + fibonacci_number(x - 1I)

n-ナッチ数は

と定義できるので、下のようなプログラムで計算できます。Seq.sum_by関数によって整数区間[x-n, x-1]F(n)xを適用した結果の総和を求めています。

let rec n_nacci_number (n:bigint) (x:bigint) =

    match x with

    | x when x <= n - 2I -> 0I

    | x when x  = n - 1I -> 1I

    | x                  -> Seq.sum_by (fun k -> n_nacci_number n k) [x - n .. x - 1I]

pizyumi
プログラミング歴19年のベテランプログラマー。業務システム全般何でも作れます。現在はWeb系の技術を勉強中。
スポンサーリンク

-F#