お気楽 F# プログラミング超入門

はじめに

関数を定義するとき、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。

ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。ですが、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。

再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。とくに関数型言語の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。

●再帰定義の基本

まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 1 に示します。

\( n! = \begin{cases} 1 & \mathrm{if} \ n = 0 \\ n \times (n-1)! & \mathrm{if} \ n \gt 0 \end{cases} \)

図 1 : 階乗の定義

階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。リスト 1 を見てください。

リスト 1 : 階乗

let rec fact n =
  if n = 0L then 1L else n * fact (n - 1L)

関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact (n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。F# の場合、関数を再帰呼び出しする場合は let の後ろに rec をつけます。rec がないとエラーになります。ご注意ください。

それでは、本当にこれで階乗を計算できるのか、実際に試してみましょう。

> let rec fact n =
-   if n = 0L then 1L else n * fact (n - 1L);;
val fact: n: int64 -> int64

> fact 9;;
val it: int64 = 362880L

> fact 10;;
val it: int64 = 3628800L

> fact 11;;
val it: int64 = 39916800L

> fact 12;;
val it: int64 = 479001600L

確かに階乗の答えを求めることができました。

●再帰定義のポイント

それでは、再帰定義のポイントを説明しましょう。図 2 を見てください。

Call:1    -->  Call:2    -->  Call:3    --> Call:4    --> Call:5
n:4            n:3            n:2           n:1           n:0
value 24  <--  value : 6 <--  value : 2 <-- value : 1 <-- value : 1 

        図 2 : fact の再帰呼び出し（n:引数の値, value:返り値

図 2 は関数 fact 4 の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出し (Call:2) では、引数 n は 3 に束縛されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。

関数の引数は局所変数として扱われます。前回説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。関数呼び出しが行われるたびに新しい局所変数を生成して、そこに値を束縛します。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。

プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact 4 を実行しているときの n は 4 であり、fact 3 を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を束縛するのです。

同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの停止条件といいます。ここが第 2 のポイントです。

停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、F# であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。

fact 0 は 1 を返して fact 1 に戻ります。fact 1 を実行しているあいだ、引数 n の値は 1 です。したがって、fact 1 の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact 4 の値 24 を求めることができます。

●累乗の計算

それでは簡単な例題として累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。

pow (x, y) = x ** y

x ** 3 = x * x * x;
x ** 4 = x * x * x * x;
x ** 5 = x * x * x * x * x;

  図 3 : 累乗の計算

今回のプログラムは、引数 x を実数、y を整数とします。そうすると、x ** y は次のように定義することができます。なお、本ページは数式の表示に JavaScript のライブラリ MathJax を使用しています。MathJax では累乗を \(x^y\) と表示します。

\( x^y = \begin{cases} 1 & \mathrm{if} \ y = 0 \\ x \times x^{y-1} & \mathrm{others} \end{cases} \)

図 4 : 累乗の定義

階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。

リスト 2 : 累乗 (1)

let rec pow (x, y) =
  if y = 0 then 1.0 else x * pow (x, y - 1)

> let rec pow (x, y) =
-   if y = 0 then 1.0 else x * pow (x, y - 1);;
val pow: x: float * y: int -> float

> pow (2.0, 32);;
val it: float = 4294967296.0

> pow (2.0, 64);;
val it: float = 1.844674407e+19

> 2.0 ** 64;;
val it: float = 1.844674407e+19

再帰定義を使って x ** y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、関数型言語では単純な繰り返しでも再帰定義を使って実現します。

●累乗の高速化

関数 pow は n 回の掛け算をしなくてはいけませんが、式を変形するともっと少ない回数で累乗を求めることがでます。次の式を見てください。

x ** 4  = (x ** 2) ** 2 -> 2 回
x ** 8  = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回

一般化すると

x ** y = (x ** (y / 2)) ** 2       （n は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （n は奇数）

        図 5 : 累乗の高速化

階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。

リスト 3 : 累乗 (2)

let rec pow (x, y) = 
  if y = 0 then 1.0
  else if y % 2 = 0 then pow (x, y / 2) * pow (x, y / 2)
  else x * pow (x, y / 2) * pow (x, y / 2)

y が偶数の場合でも奇数の場合でも、pow (x, y / 2) を 2 回呼び出していますね。同じ計算を 2 回しているのは無駄なので、let を使って局所変数を定義します。次のリストを見てください。

リスト 4 : 累乗 (3)

let rec pow (x, y) =
  if y = 0 then 1.0
  else 
    let z = pow (x, y / 2)
    let zz = z * z
    if y % 2 = 0 then zz else x * zz

let で局所変数 z と zz を定義します。z の値は x ** (y/2) です。これは pow を再帰呼び出しすれば簡単に求めることができます。zz の値は z ** 2 になります。あとは、y が偶数であれば、zz をそのまま返し、奇数であれば x *. zz を返します。このように、局所変数 z に pow (x, y / 2) の値を求めておくことで、累乗を効率的に計算することができます。

●フィボナッチ関数

もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。

\( fibo(n) = \begin{cases} 0 & \mathrm{if} \ n = 0 \\ 1 & \mathrm{if} \ n = 1 \\ fibo(n - 1) + fibo(n - 2) & \mathrm{if} \ n \gt 1 \end{cases} \)

0, 1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列

図 6 : フィボナッチ関数の定義

フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。

リスト 5 : フィボナッチ関数

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

関数 fibonacci は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibonacci の呼び出しをトレースすると下図のようになります。

f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
     │      │      │      │
     │      │      │      └ f(0)
     │      │      └ f(1)
     │      └ f(2) ┬ f(1)
     │              │
     │              └ f(0)
     │
     └ f(3) ┬ f(2) ┬ f(1)
             │      │
             │      └ f(0)
             └ f(1)

    図 7 : fibonacci のトレース

同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。

●ユークリッドの互除法

フィボナッチ関数は二重再帰でプログラムしたので実行速度はとても遅いのですが、再帰定義を使うと非効率的なプログラムになるというわけではありません。累乗のプログラムのように、再帰定義でも効率的なプログラムを作ることができます。たとえば、負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ってみましょう。まず最初に、ユークリッドの互除法を説明します。

[ユークリッドの互除法]
負でない整数 \(a, b \ (a \gt b)\) で、\(a\) を \(b\) で割った余りを \(r\) とする。
このとき、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい。

ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。

\(a = q \times b + r \quad \quad (1)\)

ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。

\(m \times a' = q \times m \times b' + r \quad \quad (2)\)

左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。

\(m \leq m' \quad \quad (3)\)

次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。

\(a = q \times m' \times b'' + m' \times r' \quad \quad (4)\)

右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。

\(m' \leq m \quad \quad (5)\)

式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。

あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。

プログラムは再帰定義を使って簡単に作ることができます。リスト 6 を見てください。

リスト 6 : 最大公約数

let rec gcd (a, b) =
  if b = 0 then a else gcd (b, a % b)

関数 gcd は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ gcd を再帰呼び出しして、b と a mod b の最大公約数を求めます。リスト 6 はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。

それでは実行例を示しましょう。

> gcd (42, 30);;
val it: int = 6

> gcd (15, 70);;
val it: int = 5

最小公倍数は最大公約数を使って簡単に求めることができます。リスト 7 を見てください。

リスト 7 : 最大公倍数

let lcm (a, b) = a * b / gcd (a, b)

整数 a と b の最小公倍数は a * b / gcd(a, b) で求めることができます。実行例を示します。

> lcm(5, 7);;
val it: int = 35

> lcm(14, 35);;
val it: int = 70

●組み合わせの数

次は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数を \({}_n \mathrm{C}_r\) と表記します。\({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。

\( {}_n \mathrm{C}_r = \dfrac{n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1)}{1 \times 2 \times 3 \times \cdots \times r} = \dfrac{n!}{r! \times (n-r)!} \)

皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。F# の整数 (int) は 32 bit 整数、int64 は 64 bit 整数なので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。

\( {}_n \mathrm{C}_r = \begin{cases} 1 & \mathrm{if} \ r = 0 \\ 1 & \mathrm{if} \ r = n \\ {}_n \mathrm{C}_{r-1} \times (n - r + 1) \div r & \mathrm{if} \ r \gt 0 \end{cases} \)

この式は _nＣ_r と _nＣ_r-1 の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。

リスト 8 : 組み合わせの数を求める

let rec comb (n, r) =
  if n = r || r = 0 then 1
  else comb (n, r - 1) * (n - r + 1) / r

とても簡単ですね。しかしながら、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。

> comb (26, 13);;
val it: int = 10400600

> comb (28, 14);;
val it: int = 40116600

> comb (30, 15);;
val it: int = -131213633

型が int の場合、comb (30, 15) で桁あふれが発生して、結果は負の値になりました。このプログラムを実際に使う場合は、桁あふれに十分注意してください。多倍長整数 (bigint) を使うと、桁あふれを気にせずに組み合わせの数を求めることができます。

●ハノイの塔

再帰といえば忘れてはいけないのが「ハノイの塔」でしょう。ハノイの塔は棒に刺さっている円盤を、次に示す規則に従ってほかの棒にすべて移動させる問題です。

1 回に 1 枚の円盤しか動かせない。
小さな円盤の上に大きな円盤を乗せることはできない。
最初は 1 本の棒に、大きい円盤の上に小さな円盤が順番に刺さっている。

ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、5 番目の円盤を左から中央の棒に移す場合、その上の 4 枚の円盤を右の棒に移しておけば、5 番目の円盤を動かすことができるようになります。そして、5 番目の円盤を中央に移したら、右の棒に移した 4 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。

n - 1 枚の円盤を左から右に移す
n 枚目の円盤を左から中央へ移す
n - 1 枚の円盤を右から中央へ移す

これを素直にプログラムすると次のようになります。

リスト 9 : ハノイの塔

let print_hanoi (from, to_) =
  printfn "from %s to %s" from to_

let rec hanoi (n, from, to_, via) =
  if n = 1 then print_hanoi (from, to_)
  else begin
    hanoi (n - 1, from, via, to_);
    print_hanoi (from, to_);
    hanoi (n - 1, via, to_, from)
  end

n は動かす円盤の枚数、from は移動元の棒、to_ は移動先の棒、via は残りの棒を示します。円盤の枚数が 1 枚の場合は簡単です。from にある円盤を to_ へ移すだけです。これが再帰の停止条件になります。移動手順を関数 print_hanoi で表示します。

●unit 型と逐次実行

printf と printfn は書式付き出力関数といい、Ｃ言語の関数 printf() と同じです。基本的には第 1 引数の書式文字列を画面へ表示します。printfn は最後に改行を出力します。書式についてはあとで詳しく説明します。次の例を見てください。

> printfn "hello, world";;
hello, world
val it: unit = ()

printfn は画面に文字列を出力する「副作用 (side effect)」が目的の関数です。hello, world は出力結果であり、printfn の返り値ではありません。() が printfn の返り値で、これを「ユニット (unit)」といいます。unit 型のデータは () しかなく、printfn のように副作用が目的の関数の返り値などで使用されます。

円盤が複数枚ある場合、from にある円盤の n - 1 枚を via に移します。この処理は hanoi を再帰呼び出しすればいいですね。次に、残りの 1 枚を to_ に移します。これを print_hanoi で表示します。そして、via に移した n - 1 枚の円盤を to_ に移します。この処理も hanoi を再帰呼び出しするだけです。

このように、式を順番に実行するとき、F# は式をセミコロン ( ; ) で区切ります。これを「逐次実行」といいます。逐次実行は最後に評価した式の値を返します。それ以外の式の結果は捨てられます。このため、返り値が unit 以外の場合、コンパイル時に警告がでるので注意してください。

簡単な例を示しましょう。

> let print_foo () = printfn "foo"; printfn "bar"; printfn "baz";;
val print_foo: unit -> unit

> print_foo();;
foo
bar
baz
val it: unit = ()

引数のない関数を呼び出す場合、F# では unit を渡します。print_foo だけでは関数を呼び出すことはできません。また、逐次実行の範囲を明確にしたい場合は、複数の式を begin ... end で囲みます。これを「コードブロック」といいます。hanoi の場合、if 式の else 節を begin ... end で囲まないと正常に動作しません。ご注意ください。

begin ... end には軽量構文があります。複数の式をカッコで囲んで、式のインデントを揃えます。このとき、式をセミコロンで区切る必要はありません。

リスト : コードブロックの軽量構文

let f () = 
  (
    式1
    式2
    式3
    ...
  )

これでプログラムは完成です。それでは実行してみましょう。

> hanoi (3, "A", "B", "C");;
from A to B
from A to C
from B to C
from A to B
from C to A
from C to B
from A to B
val it: unit = ()

●問題

次の関数を再帰を使って定義してください。

hello, world を n 回表示する関数 print_hello n
文字列 fsharp を n 行 m 列に表示する関数 print_fsharp n m
整数 1 から n までの総和を求める関数 sum n
整数 1 から n までの平方数の総和を求める関数 square_sum n
整数 1 から n までの三乗数の総和を求める関数 cube_sum n

●解答

> let rec print_hello n =
-   if n = 0 then ()
-   else (
-     printfn "hello, world"
-     print_hello (n - 1)
-   );;
val print_hello: n: int -> unit

> print_hello 10;;
hello, world
hello, world
hello, world
hello, world
hello, world
hello, world
hello, world
hello, world
hello, world
hello, world
val it: unit = ()

> let rec print_fsharp_line m =
-   if m = 0 then printfn ""
-   else (
-     printf "fsharp "
-     print_fsharp_line (m - 1)
-   );;
val print_fsharp_line: m: int -> unit

> print_fsharp_line 5;;
fsharp fsharp fsharp fsharp fsharp
val it: unit = ()

> let rec print_fsharp (n, m) =
-   if n = 0 then printfn ""
-   else (
-     print_fsharp_line m
-     print_fsharp (n - 1, m)
-   );;
val print_fsharp: n: int * m: int -> unit

> print_fsharp (3, 4);;
fsharp fsharp fsharp fsharp
fsharp fsharp fsharp fsharp
fsharp fsharp fsharp fsharp

val it: unit = ()

> let rec sum n =
-   if n = 0 then 0
-   else n + sum (n - 1);;
val sum: n: int -> int

> sum 10;;
val it: int = 55

> sum 1000;;
val it: int = 500500

> let square x = x * x;;
val square: x: int -> int

> let rec square_sum n =
-   if n = 0 then 0
-   else square n + square (n - 1);;
val square_sum: n: int -> int

> square_sum 10;;
val it: int = 181

> square_sum 100;;
val it: int = 19801

> let cube x = x * x * x;;
val cube: x: int -> int

> let rec cube_sum n =
-   if n = 0 then 0
-   else cube n + cube_sum (n - 1);;
val cube_sum: n: int -> int

> cube_sum 10;;
val it: int = 3025

> cube_sum 100;;
val it: int = 25502500