授業資料/12 の変更点

追加された行はこの色です。
削除された行はこの色です。
授業資料/12 へ行く。
授業資料/12 の差分を削除
#contents

//  第 12 回 (Ruby 関数, 再帰)

&br;&br;
* 関数の魔法: 再帰定義 [#z9c9eab1]

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

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

まず，対象となる関数を自分自身を呼び出す形で「数学的に」定義しなおす．
この ''sum'' の例だと，(n を正整数として)次のようにできることをまず理解しよう．
&br;&br;
&ref(./sum.png);
&br;&br;
&ref(/materials/warning.png); 左辺を定義する式である右辺に，左辺と同じ ''sum'' 関数が登場していることに着目すべし．

&br;&br;
CENTER:&size(24){''再帰定義が成り立つには?''};
&br;&br;

この再帰定義が「意味を持つ」には以下のポイントが満たされていることが必要である．よく考えてみよう．
+ ''左辺を右辺で置き換え，さらに右辺で置き換え… と続けていける形になっている．''
+ ''置換えの繰り返しが「必ず終わる」ようになっている''：この例だと，必ず ''n=1'' の場合に到達するようになっている．

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

さて，再帰定義の意味はわかったとして，これをプログラムで利用するにはどうするかを学ぼう．
実は使い方は簡単で，「ほぼそのまま」書けば良い．
例えばこの例の場合はプログラムを書くと次のような感じになる．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
def sum(n)
  if (n == 1) then
      return 1
    else
      return sum(n-1) + n
  end
end
}}

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

&br;&br;
** 再帰定義のなにが嬉しいの？ [#j13060f2]
&br;&br;

再帰定義の最大の利点はつぎのものである．
&br;&br;
CENTER:&ref(/materials/OK.png);&size(24){''再帰定義は「定義を書くだけでよい」.''};
CENTER:&size(24){''計算手順をプログラムしなくて良い.''};
&br;&br;

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

*** ユークリッドの互除法 [#aa8190f7]

二つの正整数 ''n, m'' (n >= m) の最大公約数を考えよう．
この時，数学的に次の性質が成り立つ(知らない人は調べよう)．
&br;&br;
CENTER:&size(18){''n と m の最大公約数は m と (n mod m) の最大公約数に等しい''};
&br;&br;
(mod は「余り」という意味だね)

&br;
よって，これを使うと二つの正整数 ''n, m'' (n >= m) の最大公約数を求める関数 ''gcd(n,m)'' について次のような再帰定義式が成り立つ．
//
&br;
&ref(./gcd.png);
&br;&br;
&ref(/materials/warning.png); この式が再帰定義の条件を満たしていることを確認しよう.

&br;&br;
これをそのままプログラミングすると以下のようになる．ただし，(n >= m) という条件を念のために確実にしておこう．そのためにちょっとだけ処理が必要だがどうやっているかは下のプログラムを読もう． 
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
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
}}

&br;&br;
&ref(/materials/notes.png); これで実際に例えば 120 と 45 の最大公約数 15 が正しく求まることを確認しよう．
&br;
&ref(/materials/warning.png); この再帰定義を「使わずに」最大公約数を求めるプログラムがどれくらい面倒なものになるか想像しよう.
&br;&br;
なお，途中の経過がよく分からないという人は，次のように途中経過を出力するように数行付け加えたプログラムを動かしてみると良い．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# 最大公約数を求める関数
def gcd(n,m)
  # 念のため，n >= m を確実にしておく.
  if (n < m) then
    n,m = m,n
  end

  # 現在 対象としているの二つの数字と，その mod を出力.
  print(n," mod ",m, " = ",n % m,"\n")

  # あとは再帰定義の式の通り.
  if (n % m == 0) then
      # 計算終了
      print("Finished. \n")
      return m
    else
      return gcd(m, (n % m) )
  end
end

# 以下，プログラム本体
n = 1071
m = 1029

# 最大公約数を関数を使って計算して表示
print("gcd(",n,", ",m,") = ",gcd(n,m),"\n")
}}

&br;&br;
** 再帰定義とループ操作との関係 [#x2f67147]

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

ということになる．

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

&br;&br;
*** 再帰とループ，どっちが得? [#b14d721d]

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

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

次に，計算の速さやコンピュータにかかる負荷についてであるが，
自分自身を何回も呼び出す仕組み上，工夫無しだと再帰定義の方が負荷が高い．
これを大きく書いておくと，
&br;&br;
CENTER:&size(24){''(素の)再帰は魔法なので MP を喰う''}; (MP = Machine Power)
&br;

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

&br;&br;
* 今日の総仕上げ [#f5f3dd6e]


+ &ref(/materials/notes.png); 階乗関数(factorial) n! を再帰定義を使って関数としてプログラムしよう．&br;
ただし，以下の条件をみたすようにしよう．
//
++ 0! = 1, 1! = 1 とする．
++ 起動時に正整数パラメータ ''n'' (30ぐらいを想定)が与えられ，0!, 1!, 2!,... n! までを出力するものとする．
++ プログラムは，再帰定義を用いて計算するとする．
//
&br;&br;
具体的には，例えばプログラムのファイル名が factorial.rb だとすると，
//
>  ruby -w factorial.rb 20
<
&br;&br;
として実行すると，
//
  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
//
という結果がでるようにしろ，ということになる．
//
&br;&br;
+ &ref(/materials/notes.png); Fibonacci 数列 ''F_0, F_1, F_2, ... '' を計算して出力するプログラムを再帰定義で書こう(Fibonacci 数列の定義を知らない人は調べよう)．
ただし，以下の条件を満たすものとする．

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

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

//
として実行すると，
   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

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

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

&br;&br;
* レポート [#kc4f5e94]

以下の課題について，あたうかぎり賢明な調査と考察と実行をし，

&size(18){''ExpMath1-Report-12''};

という題名をつけて e-mail にて教官にレポートとして提出せよ．なお，各自の

+ 所属(学部，学科)
+ 学籍番号
+ 学年
+ 氏名

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

&ref(/materials/warning.png); 自分のレポート作成ツールセットを記載せよ(もちろん，今回のレポートもそのツールセットを使って作成すること)．


** レポート課題 [#gabc5e7f]

+ 実習等で出てきた問題等に対しての，自分の解答プログラムと，その結果を示せ．
+ 1. のプログラムを「詳細に」解説せよ．


* about Icons, ClipArts [#p903245b]

For details, see [[&ref(/materials/JNorth_arrow-right-sm.png); this>materials]].

// ━┃┏┓┛┗┣┳┫┻╋


// コマンドライン入力は「行頭を > で始める」.
// コマンドライン出力は「行頭をブランクで始める」.

// 実習アイコン
// &ref(/materials/notes.png);

// 注意アイコン
// &ref(/materials/warning.png);

// Link アイコン
// &ref(/materials/JNorth_arrow-right-sm.png);

// OK アイコン
// &ref(/materials/OK.png);

// NG アイコン
// &ref(/materials/NG.png);

// サンプルアイコン
// &ref(/materials/Gnome-Preferences.png);

// 大文字での強調
// CENTER:&size(24){''ほげほげ''};

// 太文字 + 赤 での強調
// &color(red){''''};

// programu source 表記
// #highlighter(language=ruby,number=on,cache=on){{}}
//