再帰呼び出し
7月 4th, 2008 admin Posted in アルゴリズムとデータ構造 | 2 Comments » 
今日も「アルゴリズムとデータ構造シリーズ」です。本日は「再帰呼び出し」について。
再帰呼び出しとは
関数が自分自身を呼び出すのが「再帰呼び出し」。再帰が何かといわれれば、それはエッシャーの「描く手」であり落語の「頭山」でありGNUの名前の由来であったり、そしてなんといっても亜空の瘴気ヴァニラ・アイス様と答えるのが妥当でしょうか
今回は再帰呼び出しを使って2つ以上の数の最大公約数を求めるスクリプトを書きました。a,b,cと3つの数字があったら、b,cの最大公約数をもとめて、aと（b,cの最大公約数）の最大公約数を求めるというアルゴリズムです。
コード
RUBY:
-
#recursive
-
-
class Gcd
-
def initialize
-
@list = Array.new
-
end
-
-
def execute
-
multi_gcd(@list.size - 1)
-
end
-
-
def set(i)
-
@list.push(i)
-
end
-
-
#二つの数の最大公約数を求める
-
def gcd( a, b)
-
a.downto(1) do |num|
-
return num if(a%num == 0 && b%num==0)
-
end
-
nil
-
end
-
-
def multi_gcd(n)
-
#数が2以下ならgcdを呼ぶだけ
-
return self.gcd(@list[0],@list[1]) if n == 1
-
-
#数が3以上ならmulti_gcdよ呼びなおす
-
return self.gcd(@list[n], self.multi_gcd(n-1))
-
end
-
end
-
-
mg = Gcd.new
-
mg.set(9)
-
mg.set(6)
-
mg.set(27)
-
p mg.execute
まとめ
再帰をイメージするときいつも、子どもの頃に遊んだ、見た目はアイスの棒みたいな10cm幅ぐらいのロール紙の玩具を思い出します。振ると伸びて戻ってくるあれです。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
7月 6th, 2008 at 3:35:06
[...] 再帰呼び出し [...]
11月 20th, 2010 at 14:25:35
good morning, I sent an message to you about this post, its not coming thru for me. Can you connect with me when you get a chance.