更新履歴:

OCaml での再帰関数

最初の課題で、OCaml ので再帰関数の書き方で困っている人が多かっ たので、メモを置きます。なお、正確にいえば、ここでかくのは、 OCamlとは独立で、一般に再帰関数を書く、という内容です。 CでもJavaでもLisp/Scheme でも、考え方は同じです。(ただし、再帰関数の実行効率は 言語により異なります。これについては、この授業で後の方で「末尾再帰」と いう話題で、少しだけ出てきます。)

第一歩

再帰で関数を書く、ということは、漸化式を書くことと同じです。 これを理解しましょう。たとえば、「1からnまでの総和」を求めいたときは、 その一歩手前である「1からn-1までの総和」から、 「1からnまでの総和」を、どのように計算すればよいか考えます。 そうすると、以下の式に思いあたります。
 
「1からnまでの総和」 = 「1からn-1までの総和」 + n
これはほぼ正しいのですが、そのままプログラム化すると、うまく行きません。
 
sum n = (sum (n-1)) + n
これでは、「どんな入力に対しても停止しない関数」になります。

そこで,こうやりましょう.

 
n <=0 のとき
  「1からnまでの総和」 = 0
n > 0 のとき
   「1からnまでの総和」 = 「1からn-1までの総和」 + n
OCamlのプログラムとして書くと以下のようになります。
 
let rec sum n = 
   if n <= 0 then 0 
   else (sum (n-1)) + n
これで OK です.ためしに sum 5 の計算を、手動と OCaml とでやってみてください。

第二歩

次に、「mからnまでの総和」を求めいたとしましょう。 今度は、パラメータ(引数)が m と n の2つありますから、 漸化式を作ろうとすると、m と n のどちらから1引けばいいか選択肢がありま す。 でも、先ほどの問題と同様に考えれば、「mからn-1までの総和」を使えばよさ そうです。
 
m > n のとき
  「mからnまでの総和」 = 0
m <= n のとき
  「mからnまでの総和」 = 「mからn-1までの総和」 + n
OCamlプログラムとすると、こうなります。
 
let rec sum2 m n = 
    if m  > n then 0 
    else (sum2 m (n-1)) + n
これで OK です.ためしに sum2 2 5 を計算してみてください.

第三歩

もっと、いろいろやってみましょう。 今度は、n が素数であるかどうかを判定する関数です。 判定という意味は n が素数なら trueを返し、素数でないなら falseを返す、 ということです。(C言語等では、true/falseは 1/0 であらわしますが、 OCamlでは true/false と 1/0 は別なので、ここでは true/false と書きます。)

これを漸化式で書けるでしょうか?

 
  「nが素数である」 = 「n-1が素数である」が真のとき 。。。 そうでないとき。。。
ちょっと書けそうもありません。n と n-1 は素数であるかどうかは独立です から、 n-1 が素数かどうかわかったところで、n が素数かどうかはよくわかりません。

そこで、問題を少し変形して、 「n が、2,3,4,...,k のすべてで割り切れないかどうか判定する」としてみましょう。 この問題が解けると、k=n-1 とすれば、元の問題である 「nが素数かどうかを判定する」ことができます。

 
「n が、2,3,4,...,k のすべてで割り切れない」
    = 「n が、k で割り切れない」
       かつ
       「n が、2,3,4,...,k-1 のすべてで割り切れない」
漸化式で書くことができました。 ただし、このままだと、また、停止しない関数になってしまうので、 2<=k であるか、 k < 2 であるかで場合分けしてから、OCamlになおします。 この関数名を notdivall_upto とすると、
 
let rec notdivall_upto n k = 
   if k < 2 then true
   else 
      (n mod k <> 0) && (notdivall_upto n (k-1))
となります。 ここで e1 && e2 は、論理式でいうところの「e1 かつ e2」を表します。 また、n mod k <> 0 は「n を k で割ったときの余りが 0 でないこと、 つまり、n が k で割り切れないこと」を意味します。 さて、notdivall_upto ができると、素数判定は簡単にできます。
 
let isprime n = 
   notdivall_upto n (n-1)
関数isprime は再帰呼び出しをしていないので、let rec でなくて let で構いません。(let rec でも構いませんが。)

第4歩: パラメータを増やしていくパターン

今度は、「n 以上の最小の素数を求める」関数を書きましょう。 漸化式で書けるでしょうか?
 
「n 以上の最小の素数」 =  「n-1以上の最小の素数」。。。
あれ、うまく書けません。 「n-1以上の最小の素数」が n-1 そのものだったとき、困ります。(そんな計 算をしても「n以上の最小の素数」はまったくわかりませんから。) ここで、人間がなにをやるかを考えてみると、「n以上の最小の素数」を計算 するためには、 まず、n が素数かどうか試して、それが素数でなければ、次に n+1 を試しま すね。なるほど、n-1 でなく n+1 を見にいけばいいのです。「漸化式」風に 書くとこうなります。
 
「n 以上の最小の素数」 =  if  (n が素数) then n
                       else 「n+1以上の最小の素数」
これは、いわゆる数学的な「漸化式」にはなっていませんが、 ともかく、 OCamlプログラムにしてしまいましょう。
 
let rec least_prime n = 
   if (isprime n) then n
   else least_prime (n+1)
なんと、これで OK です。このプログラムは引数 n の値がどんどん大き くなっていきますから、(プログラムの定義だけを見ると)止まらないことがあ るように思える関数ですが、我々が知っている数学的知識として、「いくらで も大きい素数がある」ということがあるので、その事実に照らすと、 どんなn を与えても必ず、いつか、停止してn以上の素数を返す関数となって います。

第5歩: さらに。。。

最後に、「n の約数のうち、n自身以外で最大のもの求める」関数を書きましょう。 漸化式で書けるでしょうか?
 
  「n の約数のうち、n自身以外で最大のもの」
     = 「n-1 の約数のうち、n-1自身以外で最大のもの」。。。。
あれ、また、うまく書けません。 n の約数と n-1 の約数は(ほぼ)無関係なので、n-1 の約数の計算が できたところで、それをつかって n の約数の計算をすることはできそうもあ りません。
そこで、人間だったら、どう計算するかな、と考えてみると、一番素朴な方法は、 (1) n を n-1で割ってみる (2) n を n-2 で割ってみる、 (3) n を n-3で割ってみる、...を繰返して最初に割り切れた数を見つけることです。 (もちろん、 n-1 から始めるよりは、(n/2)+1 ぐらいから始めた方がいいの ですが、ここでは効率は気にしないことにします。) つまり、n を固定した上で、それ以外に、n-1,n-2,n-3,... という範囲を動く 変数を持たせるとよさそうです。結局、作りたい関数は、 1引数ではなく、2引数の関数になります。
 
「n の約数のうち m 以下で最大のもの」 
   = if 「n が m で割り切れる」 then m
     else 「n の約数のうち m-1以下で最大のもの」
この関数も、計算が止まるかどうかが、ちょっと心配ですが、 考えてみれば、m が 1 まで減ったら、(n は必ず 1 で割り切れるので) そこ で停止します。

OCamlではこう書けます。

 
let rec largest_factor_upto n m =
  if (n mod m = 0) then m
  else largest_factor_upto n (m - 1)
これを使って、最初の「n の約数のうち、n自身以外で最大のもの求める」関 数は以下のように書けます。
 
let largest_factor n =
   largest_factor_upto n (n-1)

演習問題


亀山幸義