授業資料/09

前回の課題について
関数の自己言及: 再帰定義
- ユークリッドの互除法
- ループ操作との関係
今日の総仕上げ
レポート
about Icons, ClipArts

前回の課題について †

まず前回の総仕上げを再掲すると，以下のようであった．

n x m 行列のデータを入力したら，その行列と転置行列をそれっぽく表示するプログラムを書こう．
もちろん，任意のサイズの行列に対して動作しないといけない！
ただし，行列の形になっていないデータは想定しなくても良い．

↑

全体構造 †

なにはともあれ，最初は全体構造からである．
今回の場合，行列の転置操作なども必要なので，それも考慮すると例えば次のようになるだろう．

こう書いてしまうと残った処理はごく簡単なことが分かる．

↑

入力データを行列として扱う †

まずは，入力された「行データ」を行列に足し込む処理部分を完成させよう．そのあたりは次のようになるだろう．

# 入力を促す
print("? : ")
while (x = gets) do
  x.chomp!
  data = x.split()
  data.map!{ |e| e.to_f }
  # この上までは決まったパターン.

  # 行データを push するだけでよい！！
  matrix.push(data)

  # 入力を促す
  print("? : ")
end

↑

行列の転置操作 †

あとは転置処理だけだ．これももう今となっては簡単で，次のようになるだろう．

def transposed_mtx(m_a)
  # 考えると，縦横のサイズは下の方法で得られる．
  n = m_a.size
  m = m_a[0].size

  # 転置行列のもとを作る．
  m_b = Array.new(m){ Array.new(n){0.0} }
  
  # 中身を入れていくだけ.
  for i in 1..n do
    for j in 1..m do
      m_b[j-1][i-1] = m_a[i-1][j-1]
    end
  end

  # 転置行列を出力．
  return m_b
end

やってみればこれだけの話だ．難しくないだろう．

↑

関数の自己言及: 再帰定義 †

さて，Ruby などのある程度真っ当な言語では，非常に便利な機能「関数の再帰定義」が可能である．
そこで，この再帰定義について学ぼう．

まず用語の説明をしておくと，関数の再帰定義が可能とは，「関数の定義文中に，自分自身の呼び出しが使える」というものである．
といってもピンと来ないだろうから，例を使って説明しよう．

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

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

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

再帰定義が成り立つ条件とは?

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

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

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

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

def sum(n)
  if (n == 1) then
      return 1
    else
      return sum(n-1) + n
  end
end

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

さて，再帰定義のなにが便利なのかを示そう．鋭い学生にはもうわかると思うが，再帰定義の最大の利点はつぎのものである．

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

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

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

↑

ユークリッドの互除法 †

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

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

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

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

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

def gcd(n,m)
  # 念のため，n >= m を確実にしておく.
  if (n < m) then
    n,m = m,n
  end

  # あとは再帰定義の式の通り.
  if (n % m == 0) then
      return m
    else
      return gcd(m, (n % m) )
  end

end

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

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

↑

ループ操作との関係 †

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

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

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

ということになる．

↑

ループを再帰で書き直す例 †

例えば，先の Fizz Buzz 関数で数字が何回変換されたかをチェックするプログラムを再帰定義を使って書き換えると以下のようになる．

while ループの代わりに再帰定義が使われている部分に特に着目して，理解しよう．

↑

再帰をループで書き直す例 †

例えば最初の再帰定義の例である sum 関数も，for ループで書き直すのは簡単だ．
また, ユークリッドの互除法も同様に適切なループで書き換え可能である．

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

↑

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

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

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

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

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

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

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

↑

今日の総仕上げ †

Fibonacci 数列 F_0, F_1, F_2, ... を計算して出力するプログラムを「二つ」書こう(Fibonacci 数列の定義を知らない人は調べよう)．
ただし，以下の条件を満たすものとする．

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

具体的には，例えばプログラムA のファイル名が fibonacciA.rb だとすると，

 ruby -w fibonacciA.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

という結果がでるようにしろ，ということになる．

プログラムが二つできたら，両方実行して「答えがおなじになること」「計算速度が違うこと」をきちんと確かめよう．また，プログラムの作り易さの違いについても考察しておこう．

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

↑

レポート †

本日受けた講義および行った実習について，簡単にまとめた報告をせよ.
また，総仕上げの部分で自分で書いたプログラムを報告せよ.

もちろん各自の

所属(学部，学科)
学籍番号
学年
氏名
日時
肝心のレポート内容(得た知見，作業について気づいたこと等も)

を書くのを忘れないように.

↑

about Icons, ClipArts †

Some icons in this page are downloadable at ICONFINDER.

The "note" icon designed by Marco Martin is distributed with the LGPL licence,
the "warning" icon designed by Alexandre Moore with the GPL licence
and the "triangle" icon designed by Joseph North is distributed with the Creative Commons (Attribution-Noncommercial-Share Alike 3.0 Unported) licence.

Some clip arts used in this page are downloadable at Open Clip Art Library.
We deeply appreciate their superb works. With licence, they describe that "the actual clipart content on open clipart library is Public domain" in the web.

添付ファイル:

sum.png 130件 [詳細]

gcd.png 150件 [詳細]