Ruby、同じことの繰り返しは君に任せるよ

もし問題が同じパターンの繰り返しを含んでいて、その極限の解が明らかならば、その問題の解決には再帰が使えるかもしれない。

再帰はある問題の答えの中にその問題自体を含む不思議な構造だ。「GNU」は「GNU’s Not UNIX」の頭文字からなる略称だ。ここで「GNU」は問題であり、その答え「GNU’s Not UNIX」の中に問題自体が含まれている。だからGNUは明らかに再帰だ。

「これじゃ答えになってない」

「つまり再帰は問題解決の役には立たない」

そういう声が聞こえてきそうだ。

つまりあなたは「GNU’s Not UNIX」が、「(GNU’s Not UNIX)’s Not UNIX」になることを知っており、「((((GNU’s Not UNIX)’s Not UNIX)’s Not UNIX)’s Not UNIX)’s Not UNIX」になることも知っており、したがって”どこまで行っても望みの答えは得られない”、ということに既に気がついているということだ。

その通り！素晴らしい！

確かにGNUの意味はどこまで行っても得られないけど、それは再帰における極限の解が明らかにされていないからだ。仮にGNUの再帰を100回繰り返せば、「GNUはUNIXになる」とでもいう極限条件が与えられれば、答えは一応得られる(釈然とはしないけれども…)。

GNUのことは諦めて「階乗」のことについて考えてみよう。

階乗は自然数nに対する1からnまでの自然数の総乗を言う¹。つまり5の階乗5!は、

5! = 1 * 2 * 3 * 4 * 5 = 120

となる。

これをRuby1.9では以下のように書ける。

   1  class Integer
   2    def !
   3      (1..self).inject(:*)
   4    end
   5  end
   6  
   7  puts 5.!
   8  # >> 120

一方、5の階乗は以下のようにも表現できる。

5! = 5 * 4!

つまり5の階乗は5に4の階乗を掛けたものとして表現できる。

これはGNUの場合と同様に答えになっていない。5!がわからないのと同様に4!なんてものもわからないからだ。でもそう、これこそが再帰のマジックなんだ。

幸いなことにGNUの場合と異なって、階乗の極限値ははっきりしている。

1! = 1

だから階乗計算は再帰で解くことが出来るんだ。

Rubyではこれらの式をそのまま書ける。

   1  class Integer
   2    def factorial
   3      return 1 if self == 1
   4      self * (self-1).factorial
   5    end
   6  end
   7  
   8  puts 5.factorial
   9  # >> 120

もう少し凝って以下のようにしてもいい。

   1  class Integer
   2    def 階乗
   3      self * (self == 1 ? 1 : (self-1).階乗)
   4    end
   5  end
   6  
   7  puts 5.階乗
   8  # >> 120

でも、階乗計算なんて会計用電卓のhp12cにだって簡単にできるんだから、ちっともうれしくない。

それじゃあもう一歩進んで、

「ハノイの塔」をやってみよう！

ハノイの塔は3本のポールと、サイズの異なる複数枚のドーナツ円盤を使ったパズルだ。スタートのポールに重ねられたすべての円盤を予備のポールを活用しながら、ゴールとなるポールにすべて移動できれば正解だ。移動は一枚ずつ行い、如何なるときも小さい円盤を大きい円盤の下に置いてはいけない²。

最小の円盤を1として、ポールの名前を(Start, Goal, Temp)とした場合、2枚の円盤(1、2)のハノイの答えは次のようになる。

円盤1をStartからTempへ移動する。

円盤2をStartからGoalへ移動する。

円盤1をTempからGoalへ移動する。

3枚の円盤(1、2、3)のハノイの答えは次のようになる。

円盤1をStartからGoalへ移動する。

円盤2をStartからTempへ移動する。

円盤1をGoalからTempへ移動する。

円盤3をStartからGoalへ移動する。

円盤1をTempからStartへ移動する。

円盤2をTempからGoalへ移動する。

円盤1をStartからGoalへ移動する。

まずはハノイの塔が再帰でいけるか検討してみる。答えの中に問いが含まれており、極限の答えがはっきりしていれば再帰でいける。

例えば、円盤3枚の場合の問いをhanoi(3)とした場合、

hanoi(3) = 3 * hanoi(2)

のような、答えの中に問いが含まれている形になればいい。

一方、極限の答えはわかっている。円盤が0のとき(n=0)は動かすものが何もないのだから。

hanoi(0) = 何もしない

となる。

じゃあ円盤が1枚(n=1)のときはどうなるだろう。

hanoi(1) = ”円盤1をStartからGoalに移動する”

円盤が1枚しかない場合の最適な移動はこれ以外にない。

そうすると円盤が複数枚(n枚)ある場合の移動に関して、以下のような手順が見えてくる。

Startにある一番下の円盤nをGoalに移動できるようにするため、その前の手順として、他のすべての円盤(1～n-1)の束をどうにかしてTempに一旦移動させる

そして、Startにある一番下の円盤nをGoalに移動する

その後、Tempに置いた他の円盤(1～n-1)の束をすべてどうにかしてGoalに移動させる

ここで1.に注目すると、これはまさにn-1枚の円盤をStartからTempに移動させるというハノイの問題だ！また3.に注目すると、これもまたn-1枚の円盤をTempからGoalに移動させるというハノイの問題だ！

つまりハノイの問題はその答えにハノイの問題を含んだ再帰的なものになる！そしてその極限の値n=0の答えは明らかだ。よって「ハノイの塔」は再帰で解くことができる！

これをもう少しまとめると、hanoi(n)の答えは以下のようになる。

hanoi(n) =
         1. n = 0 のときは何もしない,
         2. hanoi(n-1)を求める。但し移動はStart => Temp,
         3. "円盤nをStartからGoalへ移動する”,
         4. hanoi(n-1)を求める。但し移動はTemp => Goal

これをRubyで記述してみる。

   1  POLES = ['Start', 'Goal', 'Temp']
   2  
   3  def hanoi(n, from=POLES[0], to=POLES[1])
   4    temp = (POLES - [from, to]).to_s
   5    return if n == 0
   6    hanoi(n-1, from, temp)
   7    puts "move #{n} #{from} => #{to}"
   8    hanoi(n-1, temp, to)
   9  end
  10  
  11  hanoi(3)
  12  
  13  # >> move 1 Start => Goal
  14  # >> move 2 Start => Temp
  15  # >> move 1 Goal => Temp
  16  # >> move 3 Start => Goal
  17  # >> move 1 Temp => Start
  18  # >> move 2 Temp => Goal
  19  # >> move 1 Start => Goal

せっかくだから円盤をA,B,C,…として、Hanoiクラスも書いてみよう。

   1  class Hanoi
   2    POLES = ['Start', 'Goal', 'Temp']
   3    DISCS = ('A'..'Z').to_a
   4  
   5    def initialize(n)
   6      @n = n
   7      @from = POLES[0]
   8      @to = POLES[1]
   9      @cnt = 0
  10      @result = []
  11    end
  12    
  13    def steps
  14      @result = []
  15      hanoi(@n, @from, @to)
  16    end
  17    
  18    def to_s
  19      @result = []
  20      answer = ""
  21      result = hanoi(@n, @from, @to)
  22      result.each_with_index do |(disc,from,to), i|
  23        answer << "#{i+1}: move #{DISCS[disc-1]} #{from} => #{to}\n"
  24      end
  25      answer
  26    end
  27    
  28    private
  29    def hanoi(n, from, to)
  30      tmp = (POLES - [from, to]).to_s
  31      return @result if n == 0
  32      hanoi(n-1, from, tmp)
  33      @cnt += 1
  34      @result << [n, from, to]
  35      hanoi(n-1, tmp, to)
  36    end
  37  end
  38  
  39  if __FILE__ == $0
  40    h = Hanoi.new(3)
  41    puts h
  42  end
  43  # >> 1: move A Start => Goal
  44  # >> 2: move B Start => Temp
  45  # >> 3: move A Goal => Temp
  46  # >> 4: move C Start => Goal
  47  # >> 5: move A Temp => Start
  48  # >> 6: move B Temp => Goal
  49  # >> 7: move A Start => Goal

Rubyを使って再帰とハノイの塔を勉強したので、それをまとめてみました。参考になればうれしいです。

(参考サイト)

再帰的アルゴリズム

第１７章再帰的手続き　他

(追記:2008/7/10)Hanoiクラスを少し修正しました

[階乗 - Wikipedia](http://ja.wikipedia.org/wiki/%E9%9A%8E%E4%B9%97 ↩
[ハノイの塔 - Wikipedia](http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94 ↩

blog comments powered by Disqus

100円〜で好評発売中！
M'ELBORNE BOOKS

Ruby、同じことの繰り返しは君に任せるよ 再帰でハノイの塔を解こう!

Ruby、同じことの繰り返しは君に任せるよ再帰でハノイの塔を解こう!