再帰プログラム入門

懇切丁寧、微に入り細を穿ちて著されればRuby及びプログラミングの両者が目的に共に入門書としてお誂え向きとて愛読の 初めてのプログラミング の各章の最後に設けられた練習問題では正解の掲載されぬを、 幾許か不安を感じるも在り哉無し哉、共に本誌をご愛読の同志に捧ぐ、 当ブログに於いては参照、比較検討用に生贄的に供す個人的な解釈、解答を掲載す為の本カテゴリー 初めてのプログラミング に於いて前回に当たる2009年01月26日のアーティクル メソッドの作り方(「新しい」ローマ数字)於Ruby にて第9章迄を終え、当回より入りたる第10章
10章 再帰とこれまでの復習
10.1 再帰
10.2 通過儀礼:並べ替え(ソート)
10.3 練習問題
10.4 例をもう1つ
10.5 追加練習問題
が冒頭には
おめでとう! あなたはプログラマです! この時点でプログラミングの基礎をほとんどカバーしました。
とあるは、何たる時宜を得た励まし、 此の激励を背に秘かな矜持を胸に進めば提示さる
自分自身を呼び出すメソッドを書いたとしたら、どうなるでしょう?? それが再帰(recursion)です。
が軽やかに合点されます。 再帰の例を挙げる際には階乗を用いると云う不文律を諧謔を交えて説明され、 其の後に例として上げられる大陸の大きさの測り方抔も実に楽しくあります。 扠、そうこうする内進む10.2では何やら通過儀礼と題目も恐ろしきは提出される課題の 練習問題にはあらねど今回は此方への当方の解答例を贄に供すべく思います。
スポンサーリンク
此処に著者より唐突に記憶を辿らさせしめらるは本書73頁の並べ替えにつき、 其れに関しては当ブログは2008年12月21日のアーティクル 初めてのプログラミング5(イテレータ) にて言及致しましたソートプログラムの課題に取り組む際利用した配列の sortメソッド を自ら実装せよ、と云うのが通過儀礼になる様です。 此の際、アルファベット順に順位を付けるには、 >:大なり
<:小なり
を用いれば宜しいとのヒントが与えられます。 作成プログラムは再帰の利用の有無で二本が要請されます。 どうやら先ずは whileループ を用いて要求機能を満足し、 其れを再帰を用いたものに改訂すれば良い様です。

上記を受け、先ず書いて見たものが下記になります。
# アルファベット順ソート関数(非再帰)

def word_sort_self unsorted_array, sorted_array
  tmp_sorted_array = []
  least = nil # 最小値単語

  while unsorted_array != []
    if least == nil
      least = unsorted_array.pop
    end

    comparison = unsorted_array.pop # 比較用単語

    if comparison
      if comparison < least
        tmp_sorted_array.push least
        least = comparison
      else
        tmp_sorted_array.push comparison
      end
    end
  end

  sorted_array.push least

  return tmp_sorted_array, sorted_array

end

# ユーザー入力取得ブロック

word = []

while word.last != ´´
  puts ´お好きな単語を入力して下さい。´
  puts ´結果閲覧したい時は何も入力しないでENTERを押して下さい。´
  word.push gets.chomp
end
word.pop


# アルファベットソート及び結果表示ブロック

ret_wod = word_sort_self(word,[])

while ret_wod[0] != []
  ret_wod = word_sort_self(ret_wod[0],ret_wod[1])
end

puts ´入力された単語をアルファベット順に並べ替えて表示します。´
puts ret_wod[1].join(´, ´)
上記プログラムを、現在の手元環境
ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]
で走らせて得られる結果は、 orange、kiwi、banana、apple、pineapple、peach の順に単語を入力すれば、
C:¥tsukamotch¥Ruby¥programs>word_sort.rb
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。
orange
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。
kiwi
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。
banana
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。
apple
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。
pineapple
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。
peach
お好きな単語を入力して下さい。
結果閲覧したい時は何も入力しないでENTERを押して下さい。

入力された単語をアルファベット順に並べ替えて表示します。
apple, banana, kiwi, orange, peach, pineapple
の最後の行の出力が apple, banana, kiwi, orange, peach, pineapple と、どうやら無事、要請機能を満たせた様です。

次に此れに再帰を利用せしむるに、 本書より与えられるヒントがラッパーメソッドを用いよと云うもので、 2つのパラメータを取るメソッドに対し空の配列を渡す手間を省く為との教示を受け、 プログラムは以下の様にしました。
# アルファベット順ソート関数(再帰)

def sort some_array
  # このメソッドは「recursive_sort」をラップする。
  # ´[]´を引数に渡すのを防ぐ為
  recursive_sort some_array, []
end


# アルファベット順ソート関数

def recursive_sort unsorted_array, sorted_array
  tmp_sorted_array = []
  least = nil # 最小値単語

  while unsorted_array != []
    if least == nil
      least = unsorted_array.pop
    end

    comparison = unsorted_array.pop # 比較用単語

    if comparison
      if comparison.downcase < least.downcase
        tmp_sorted_array.push least
        least = comparison
      else
        tmp_sorted_array.push comparison
      end
    end
  end

  sorted_array.push least

  if tmp_sorted_array != []
    return recursive_sort(tmp_sorted_array, sorted_array)
  else
    puts sorted_array.join(´, ´)
  end
end


# ユーザー入力取得ブロック

word = []

while word.last != ´´
  puts ´お好きな単語を入力して下さい。´
  puts ´結果閲覧:無入力=>ENTER押下´
  word.push gets.chomp
end
word.pop


# アルファベットソート及び結果表示ブロック

sort(word)
個人的な感覚としては随分とクリアーと云うか、見通しが付き易くなった気がするのですが如何でしょうか。 扠、此れを非再帰と同じ環境で走らせれば
C:¥tsukamotch¥Ruby¥programs>word_sort_r.rb
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下
orange
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下
kiwi
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下
banana
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下
apple
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下
pineapple
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下
peach
お好きな単語を入力して下さい。
結果閲覧:無入力=>ENTER押下

apple, banana, kiwi, orange, peach, pineapple
と、どうやら此方も上手い塩梅に機能した様です。
スポンサーリンク

「再帰プログラム入門」への2件のフィードバック

  1. 完全なシャッフル

    初めてのプログラミング当カテゴリー初めてのプログラミングに投稿す度、常々其の有用性を賛美するに吝かならぬが、Ruby及びプログラミングの両者が目的に共に入門書としてお誂え向きとて愛読の初めてのプログラミングも今度は少し許り様相の異なるが訳はアーティクル後半に

  2. アルファベットソート関数ダウングレード

    初めてのプログラミング当ブログのカテゴリーにも誂える初めてのプログラミングにアーティクルを順次、Ruby及びプログラミングの両者共に入門書として有用なるとは屡ご紹介の初めてのプログラミングに従いエントリを進捗すべき図った積りが、投稿間隔の開くに因ってか、遂に

コメントは受け付けていません。