ファレイ数列 - わさっきhb

10日に一度はRubyのコード．ということで問題です．

正整数nが与えられたとき，0より大きく1未満で，分母がn以下の有理数を，小さいものから順に出力しなさい．

この出力はファレイ数列と呼ばれます．ファレイ数列について，てっとり早く知りたければ，ファレイ数列 - Wikipedia，本を読むなら『アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ 1―超入門編)』がおすすめです．
ポイントは，二つの有理数 $\frac{a}{b}$ と $\frac{c}{d}$ に対して，新たな有理数を $\frac{a+c}{b+d}$ で求めることです．それと再帰．
ではコードです．まずは素朴なもの．

#!/usr/bin/env ruby

# 分数を出力する
def put_number(a, b)
  puts "#{a}/#{b} = #{a.to_f / b.to_f}"
end

# 再帰呼び出しを使って，ファレイ数列を出力する
def generate_sequence(a1, b1, a2, b2, n)
  a3 = a1 + a2
  b3 = b1 + b2
  return if b3 > n

  generate_sequence(a1, b1, a3, b3, n); # 左半分の出力(再帰呼び出し)
  put_number(a3, b3);                   # 中間値の出力
  generate_sequence(a3, b3, a2, b2, n); # 右半分の出力(再帰呼び出し)
end

if __FILE__ == $0
  n = (ARGV.shift || 7).to_i
  generate_sequence(0, 1, 1, 1, n)
end

特別な意味はないですが，デフォルト値は7にしています．
「有理数」といえば，RubyにはRationalクラスがありますね．これを使って，書き換えてみます．

#!/usr/bin/env ruby

require "rational"

# 分数を出力する
def put_number(a)
  puts "#{a} = #{a.to_f}"
end

# 再帰呼び出しを使って，ファレイ数列を出力する
def generate_sequence(a1, a2, n)
  a3 = Rational(a1.numerator + a2.numerator, a1.denominator + a2.denominator)
  return if a3.denominator > n

  generate_sequence(a1, a3, n); # 左半分の出力(再帰呼び出し)
  put_number(a3);               # 中間値の出力
  generate_sequence(a3, a2, n); # 右半分の出力(再帰呼び出し)
end

if __FILE__ == $0
  n = (ARGV.shift || 7).to_i
  generate_sequence(Rational(0, 1), Rational(1, 1), n)
end

Rational使用版は，メソッドの引数が減ったものの，ポイントとして挙げた計算が煩雑になってしまいました．
Rational使用版には，もうひとつ，問題があります．ファレイ数列は「0/1から1/1の間」ですが，Stern-Brocot tree(英語)を求めるときに「0/1から1/0の間」として，

  generate_sequence(Rational(0, 1), Rational(1, 1), n)

のところを

  generate_sequence(Rational(0, 1), Rational(1, 0), n)

とすると，「denominator is zero (ZeroDivisionError)」というエラーが出ます．
Rational不使用版では，「generate_sequence(0, 1, 1, 1, n)」を「generate_sequence(0, 1, 1, 0, n)」にするほか，もう1箇所，修正すれば，Stern-Brocot treeも出力できます．「もう1箇所の修正」をせずに実行すると，無限ループに陥るので，そこから要修正箇所は容易につかめるでしょう．

補足

1. ファレイ数列は，今年度のCのプログラミング授業で取り上げました．上のコードは，そのCのコードをRubyで書き直したのでした．2日前に再帰の問い方 - わさっきhbというのを書きましたが，試験には使っていません．将来的には…というのはここで書かないほうがいいですね．
2. ファレイ数列を取り上げた著者の独白も興味深いです．

(略)ファレイ数列は，再帰の威力を説明するのに最適の例題だとひそかに信じているものである．白状すると，アルゴリズムの研究を長年続けていながら，再帰でしか書きにくいアルゴリズムというのを考案したことがなかった．画像に含まれる直線成分を見つける新たなアルゴリズムを提案したときに，ファレイ数列が関係することがわかり，そのプログラムを再帰を用いて実現したのが，著者にとって最初の非自明な再帰プログラムであった．再帰を用いるとプログラムが非常に簡潔になることを発見したときの感動は今でも記憶に残っている．感動は研究意欲の源泉である．
(アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ 1―超入門編), p.148)

3. 再帰というと，「スタックを使い果たさないか?」という不安がありますが，上記のコードについて，使用するスタックの段数は，最初に与える正整数nで抑えられます．手短に理由を言うと，ファレイ数列の木に対して深さ優先探索を行っているからです．