授業資料/12

関数の魔法: 再帰定義
- 再帰定義のなにが嬉しいの？
  - ユークリッドの互除法
- 再帰定義とループ操作との関係
  - 再帰とループ，どっちが得?
今日の総仕上げ
レポート
- レポート課題
about Icons, ClipArts

関数の魔法: 再帰定義 †

現代のコンピュータの高級言語の関数では，自分自身を定義に使う「再帰定義」という魔法が使える．それについて学ぼう．

sum(n) := 1 + 2 + ... + n という関数を再帰定義を使って定義してみるので，以下の例から理解しよう．

まず，対象となる関数を自分自身を呼び出す形で「数学的に」定義しなおす．この sum の例だと，(n を正整数として)次のようにできることをまず理解しよう．

左辺を定義する式である右辺に，左辺と同じ sum 関数が登場していることに着目すべし．

再帰定義が成り立つには?

この再帰定義が「意味を持つ」には以下のポイントが満たされていることが必要である．よく考えてみよう．

左辺を右辺で置き換え，さらに右辺で置き換え… と続けていける形になっている．
置換えの繰り返しが「必ず終わる」ようになっている：この例だと，必ず n=1 の場合に到達するようになっている．

定義置換えの繰り返しが「終わらない」定義を行った場合，プログラムは永遠に停止しない! 必ず定義が最終的に完結するように注意して定義しよう．

さて，再帰定義の意味はわかったとして，これをプログラムで利用するにはどうするかを学ぼう．実は使い方は簡単で，「ほぼそのまま」書けば良い．例えばこの例の場合はプログラムを書くと次のような感じになる．

さて，これで動くのだろうか? 実際に試してみよう．上の再帰定義を使って，sum(10) などが確かに正しい数字になることを確認してみよう．

↑

再帰定義のなにが嬉しいの？ †

再帰定義の最大の利点はつぎのものである．

再帰定義は「定義を書くだけでよい」.

計算手順をプログラムしなくて良い.

よく考えれば不思議なことではない．繰り返して定義を適用すればいつか必ず完結する定義なのだから，コンピュータがそうしてくれるだけなのだ．しかし，これが実際はとても便利なことが多いのだ．以下，例で理解しよう．

↑

ユークリッドの互除法 †

二つの正整数 n, m (n >= m) の最大公約数を考えよう．この時，数学的に次の性質が成り立つ(知らない人は調べよう)．

n と m の最大公約数は m と (n mod m) の最大公約数に等しい

(mod は「余り」という意味だね)

よって，これを使うと二つの正整数 n, m (n >= m) の最大公約数を求める関数 gcd(n,m) について次のような再帰定義式が成り立つ．

この式が再帰定義の条件を満たしていることを確認しよう.

これをそのままプログラミングすると以下のようになる．ただし，(n >= m) という条件を念のために確実にしておこう．そのためにちょっとだけ処理が必要だがどうやっているかは下のプログラムを読もう．

これで実際に例えば 120 と 45 の最大公約数 15 が正しく求まることを確認しよう．
この再帰定義を「使わずに」最大公約数を求めるプログラムがどれくらい面倒なものになるか想像しよう.

なお，途中の経過がよく分からないという人は，次のように途中経過を出力するように数行付け加えたプログラムを動かしてみると良い．

↑

再帰定義とループ操作との関係 †

for や while などのループではループが終わってから再びループに入る動作が主な動作だが，これは自分自身を呼び出す再帰定義と本質的には同じ行為だ．ということは，ループ計算は再帰定義で書きなおすことができるはずだし，逆もまた真のはずだ．つまり，

ループ計算は再帰定義で書き直すことが出来，

再帰定義はループ計算で書き直すことが出来るはず．

ということになる．

(時間に余裕のある人向け) ユークリッドの互除法を再帰定義を使わずにプログラミングしてみよう．

↑

再帰とループ，どっちが得? †

再帰定義とループ計算が本質的に同じなら，どちらを選ぶべきかという問題がでてくる．これについては，二つの視点がある．

まず，プログラムのわかりやすさだが，これは問題による．ユークリッドの互除法などは再帰定義がわかりやすいが，手順を示されて理解するようなタイプの計算はループの方がわかりやすいだろう．大きく書いておくと，

再帰とループのどちらがわかりやすいかは問題による

次に，計算の速さやコンピュータにかかる負荷についてであるが，自分自身を何回も呼び出す仕組み上，工夫無しだと再帰定義の方が負荷が高い．これを大きく書いておくと，

(素の)再帰は魔法なので MP を喰う (MP = Machine Power)

となる．結局，メリットもデメリットもあるので，再帰定義を使うべきかどうかはケースバイケースということになる．

↑

今日の総仕上げ †

階乗関数(factorial) n! を再帰定義を使って関数としてプログラムしよう．
ただし，以下の条件をみたすようにしよう．
1. 0! = 1, 1! = 1 とする．
2. 起動時に正整数パラメータ n (30ぐらいを想定)が与えられ，0!, 1!, 2!,... n! までを出力するものとする．
3. プログラムは，再帰定義を用いて計算するとする．
  
  具体的には，例えばプログラムのファイル名が factorial.rb だとすると，
  ruby -w factorial.rb 20
  
  として実行すると，
```
 0! = 1
 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
 10! = 3628800
 11! = 39916800
 12! = 479001600
 13! = 6227020800
 14! = 87178291200
 15! = 1307674368000
 16! = 20922789888000
 17! = 355687428096000
 18! = 6402373705728000
 19! = 121645100408832000
 20! = 2432902008176640000
```
  という結果がでるようにしろ，ということになる．
Fibonacci 数列 F_0, F_1, F_2, ... を計算して出力するプログラムを再帰定義で書こう(Fibonacci 数列の定義を知らない人は調べよう)．ただし，以下の条件を満たすものとする．

F_0 = 0, F_1 = 1 とする.
起動時に正整数パラメータ n (30ぐらいを想定)が与えられ，F_0, F_1, F_2,... F_n までを出力するものとする．
プログラムは，再帰定義を用いて計算するとする．

具体的には，例えばプログラムのファイル名が fibonacci.rb だとすると，
ruby -w fibonacci.rb 30

として実行すると，
```
  F_0 = 0
  F_1 = 1
  F_2 = 1
  F_3 = 2
  F_4 = 3
  F_5 = 5
  F_6 = 8
  F_7 = 13
  F_8 = 21
  F_9 = 34
  F_10 = 55
  F_11 = 89
  F_12 = 144
  F_13 = 233
  F_14 = 377
  F_15 = 610
  F_16 = 987
  F_17 = 1597
  F_18 = 2584
  F_19 = 4181
  F_20 = 6765
  F_21 = 10946
  F_22 = 17711
  F_23 = 28657
  F_24 = 46368
  F_25 = 75025
  F_26 = 121393
  F_27 = 196418
  F_28 = 317811
  F_29 = 514229
  F_30 = 832040
```
という結果がでるようにしろ，ということになる．

(上級者向け) 再帰定義でありながら「実行速度が速い」プログラムを書いてみよう．どうすればよいだろうか.