ある事柄の定義にそれ自身が登場することを再帰という。例えば、今日の授業は何回目かと考えた場合、「前回の回数に1を足したものである」と定義することができる。このような定義は「去年は20歳だったから今年は21歳」、「昨日は15日だったから今日は16日」というように様々な場面で登場する。

この定義にしたがう場合、回数を明らかにする定義の中に、再度回数が出現することになる。これだといつまでたっても今回の回数が明らかにならないような気がするが、「それ以上前に授業がない場合は1回目とする」という定義を付け加えれば、必ず回数は確定する。

複雑な問題を解く場合に、再帰を用いた方が簡単になる場合がある。

1からNまでの足し算

1からNまでの足し算を例に挙げ、再起について考えてみよう。

例えば、5までの足し算の場合、1+2+3+4+5とか5+4+3+2+1と書く。Nまでの足し算の場合はN+(N-1)+(N-2)+...+2+1となる。

再帰的な方法で1からNまでの計算の方法を定義してみよう。

これをプログラムで書くと下記の通りになる（recursive-sum.rb）

#!/usr/koeki/bin/ruby/
def sum(n)
  if n == 1
    1
  else
    n + sum(n-1)
  end
end

STDERR.print "好きな数字を入力してください"
number = gets.chomp!.to_i

printf ("1から%dまで足すと%dになります。\n",number,sum(number))

問題となるのはdef-endの定義内容である。特に下記の行に着目しよう。

n + sum(n-1)

sumというメソッドの定義の中で、再度sumが呼び出されている。

number=4とした場合の、このプログラムの動きを確認してみよう

1. sum(4)が呼び出される
2. sum(4)=4+sum(4-1)なのでsum(3)が呼び出される
3. sum(3)=3+sum(3-1)なのでsum(2)が呼び出される
4. sum(2)=2+sum(2-1)なのでsum(1)が呼び出される
5. sum(1)=1なのでsum(1)として1が返される
6. sum(2)=2+sum(1)なのでsum(2)として3が返される
7. sum(3)=3+sum(2)なのでsum(3)として6が返される
8. sum(4)=4+sum(3)なのでsum(4)として10が返される
9. 「1から4まで足すと10になります」と表示される

階乗の計算

階乗の計算を使って、再起についてもう少し考えてみよう。

階乗の計算とは n! で表記され n!=n*(n-1)*(n-2)*・・・2*1で表現される。例えば5の階乗であれば、5!=5*4*3*2*1となる。

再帰的な方法で階乗の計算の方法を定義してみよう。

これをプログラムで書くと下記の通りになる（factorial.rb）

#!/usr/koeki/bin/ruby/
def factorial(n)
  if n <= 1
    1
  else
    n * factorial(n-1)
  end
end

STDERR.print "好きな数字を入力してください"
number = gets.chomp!.to_i

printf ("%dの階乗は%dです\n",number,factorial(number))

問題となるのはdef-endの定義内容である。特に下記の行に着目しよう。

n * factorial(n-1)

factorialというメソッドの定義の中で、再度factorialが呼び出されている。

number=4とした場合の、このプログラムの動きを確認してみよう

1. factorial(4)が呼び出される
2. factorial(4)=4*factorial(4-1)なのでfactorial(3)が呼び出される
3. factorial(3)=3*factorial(3-1)なのでfactorial(2)が呼び出される
4. factorial(2)=2*factorial(2-1)なのでfactorial(1)が呼び出される
5. factorial(1)=1なのでfactorial(1)として1が返される
6. factorial(2)=2*factorial(1)なのでfactorial(2)として2が返される
7. factorial(3)=3*factorial(2)なのでfactorial(3)として6が返される
8. factorial(4)=4*factorial(3)なのでfactorial(4)として24が返される
9. 「4の階乗は24です」と表示される

プログラムの流れは上記の通りである。階乗の計算は比較的単純であるため、こんな複雑なことをしなくてもプログラムを書くことができそうな気がする。しかし、再帰的な方法は、複雑な処理を繰り返し行う場合には大きな力を発揮する。

再帰を使用する際のポイントは下記の通りとなる。

大小関係が定められたデータを、大きい順（降順）や小さい順（昇順）に並べ替える作業をソートという。Rubyにはsortメソッドが備わっており、ソート自体を実行するプログラムを書く必要はない。しかし、実際にはソートは奥の深いテーマであり、いかに効率的に実行するかという観点より様々な方法が提案されている。

クイックソート

n個の要素から任意の要素aを取り出す。残りの要素についてaよりも大きければ右側、小さければ左側に配置する。先頭の要素を基準として左右に振り分ける作業をクイックソートと呼ぶ。クイックソートを繰り返すことで、左右に振り分けられる値が0個もしくは1個となる。この時点で並び替えは終了となる。

この図では最初に先頭の要素である6を取り出している。そして6を基準として、6よりも大きければ右側に配置し、小さければ左側に配置している。次に左右に配置された要素について、それぞれ先頭（左は3、右は8）を基準として同様にクイックソートを行っている。

2回目のクイックソートを行った時点で、8の左側の山は値が「7」の1つのみとなっている。1つの場合はこれ以上の並び替えはできないため、これで順番が確定になる。3の左右、8の右側についてクイックソートを継続する。

3回目のクイックソートを行うと左から2つの山については順番が確定となる。一番右側の山のみまだ順番が確定していない。

一番右側の山について4回目のクイックソートを実行する。これですべての順番が確定する。

これをプログラムで書くと下記のとおりになる（quicksort.rb）。

#!/usr/koeki/bin/ruby

def quicksort(data)	# 配列(順番がばらばらなデータ)を受け取る

  if data.length <= 1	# データが1個以下なら
    data		# そのものを返して並べ換え完了
  else
    left = []	        # left(左側配列)を新規作成 left = Array.new でも可
    right = [] 	        # right(右側配列)を新規作成 right = Array.new でも可
    k = data.shift	# 配列dataの先頭を取り出してkにする(破壊的操作)

    for x in data	# 残ったdata全てに対して繰り返す
      if x < k 	   	# kより小さかったら
         left << x	# 左側に追加(<<は配列末尾への破壊的要素追加、pushと同じ)
      else
         right << x	# 右側に追加(同上)
      end               # ifに対するend
    end			# forに対するend

    quicksort(left) + [k] + quicksort(right)
    # quicksort(left) と k と quicksort(right) を合体したものが最終結果	
    # kは要素なので[]で括って配列にする
  end                   # ifに対するend
end                     # defに対するend

def ketsugo(a)          # 配列を受け取ってjoinメソッドで結合して返す
  printf("[%s]\n", a.join(", "))
end                     # defに対するend

array = []
while true              # 配列に好きな数値を順次代入
  STDERR.print "好きな数字を入力(終了はq)"
  datum = gets.chomp!
  if datum == "q"
    then break
  end
  array.push(datum.to_i)  # pushで配列arrayの末尾に追加(<<でも同じ)
end

print "もとの順番\n"
ketsugo(array)             # ketsugoメソッドの呼び出し 
print "並べ替え後\n"
ketsugo(quicksort(array))  # ketsugoメソッドの呼び出し
                           # 引数はquicksortを呼び出した結果

irsv{c10xxxx}% ruby quick_sort.rb[Return]
好きな数字を入力(終了はq)400
好きな数字を入力(終了はq)204
好きな数字を入力(終了はq)346
好きな数字を入力(終了はq)958
好きな数字を入力(終了はq)225
好きな数字を入力(終了はq)367
好きな数字を入力(終了はq)784
好きな数字を入力(終了はq)q
もとの順番
[400,204,346,958,225,367,784]
並べ替え後
[204,225,346,367,400,784,958]

10進数を2進数や16進数に変換する方法は前期に取り上げたが、この方法で10進数を他の進数に変換することもできる。以下の図を確認してみよう。

この図は前期の図とは若干形が異なっている。前期の図では商が変換したい進数未満（例えば2進数なら2未満、16進数なら16未満）になるまで割り続け、最終的な商から初めて余りを下から上に向かって読んでいくとした。

この図では、割り算の回数を1回増やし、商が0になるまで割り算を続けている。こうすると余りの部分のみ下から上に向かって読んでいけばよい。行っている作業は同じであるが、今回の図では余りだけを読めばよいので、プログラムで実装する場合には都合が良い（作りやすい）。

1、2いずれかについて解答せよ。余裕がある人はいずれも解答せよ。

1. 10進数XのY進数への変換について再帰的定義をせよ。定義を文章で書けばよい。
2. 自分の生年月日を8進数に変換せよ。例えば12月8日なら1208を8進数に変換する。メールには元の10進数と変換後の8進数のみ記載すればよい。

制限時間は10分。出席点は2点。提出要領は下記の通り。

• 提出先：naoya@e.koeki-u.ac.jp
• メールのSubject：attend08
• 本文の構成：1行目で学籍番号、氏名を記載する。2行目以降に解答を記載する。

Tips：emacsでの日本語入力のオンオフはCtrl-oです

Tips：Mewによるメールの送り方はMewコマンドを参照

以下のうちいずれかを選んで解答する。

問題1（8点満点）：これまでに作成したプログラムの中から1つを選び、自分のWebページで公開する。htmlの文法の正しさに基づき採点する。なお作成するのはhtmlファイル1つであり、その中にプログラムの概要とプログラムを記載する。デザインや概要の文章を工夫して、プログラムを実行してみたくなるようなページ作りを心がける。なお、htmlファイル作成にあたってはtext-decorationやline-heightなどのCSSのプロパティを最低でも6種類は使用すること。

問題2（8点満点）：問3を再帰を使わずに書く。def-endも使用しなくても良い。

問題3（10点満点）：キーボードから入力した任意の10進数Xを、Y進数に変換するプログラムを再帰を用いて書け。Yもキーボードから入力するが、2〜9の整数のみ入力を受け付けるようにする（つまり2進数から9進数までの変換ができるようにする）。

---

• 提出先：naoya@e.koeki-u.ac.jp
• 提出期限：12/02(日）23:59
• メールのSubject：課題6
• 本文の構成：1行目で学籍番号、氏名を記載する。2行目以降は下記の構成とする

問題1の場合

1. プログラムを掲載したWebページのURL
2. 感想

問題2、3の場合

1. 作成したプログラム
2. プログラムの実行結果
3. プログラムの説明
4. 感想

---

• 採点基準（問題1）：期限内提出点（2点）、メールの体裁（1点）、CSS・デザイン（2点）、htmlの構文（3点）：htmlの構文はAnother HTML-lint gatewayで採点し、マイナスなら0点、50点以下なら1点、100点未満なら2点、100点なら3点とする。
• 採点基準（問題2、3）：期限内提出点（2点）、メールの体裁（1点）、プログラム（2〜4点）、プログラムの説明（3点）
• プログラムの説明：問題2は進数計算をプログラムでどのように実装したかについて、問題3は再帰処理を行っている部分について、処理の流れを追いながら詳しく説明する。
• わかりにくい説明や、Webページを単にコピー&ペーストしただけの説明は減点することがある。一度読み直してから提出すること。
• 驚異的に良くできているレポートについては満点を超える得点をつけることがある。
• よくできていたレポートは、他の人の参考になるよう、本人が特定できないような形で掲載する。掲載してほしくない場合はメールでの課題提出時にその旨記載すること。

---

Tips：emacsでの日本語入力のオンオフはCtrl-oです

Tips：ktermでのプログラムの実行結果をメールに貼り付けるには、コピーしたい箇所をマウスで選択し、emacs（Mew）上でマウスの真ん中ボタンをクリックする

Tips：Mewによるメールの送り方はMewコマンドを参照