再帰呼び出しを用いたフィボナッチ数列の計算

問題

フィボナッチ数列の第n項を求めるプログラムを再帰呼出しを用いて書いて下さい。
ただしnはコマンドライン引数で得るものとします。

※こちらのサイトから引用

解答

fibonacci_number_recurrence.rb

# フィボナッチ数列を格納する配列
# 例に従い初項は0,第2項は1
$fibonacchi_array = [0,1]

# 第n項のフィボナッチ数を求めるメソッド
# term_n:求めたいフィボナッチ数列の項数
# prev_fibonacchi:1つ前のフィボナッチ数列の数（デフォルトは0）
# current_fibonacchi:現在求まっているフィボナッチ数列の数（デフォルトは1）
# 返り値:第n項のフィボナッチ数
def calc_fibonacchi(term_n, prev_fibonacchi = $fibonacchi_array[0], current_fibonacchi = $fibonacchi_array[1])
  # 第0項が指定されたらそのまま返す
  if term_n == 0
    return $fibonacchi_array[term_n]
  # term_nが1になったら最後の要素を返す
  elsif term_n == 1
    return $fibonacchi_array.last
  end

  # 求まっている最新2つの要素を足して配列の最後に加える
  $fibonacchi_array.push(prev_fibonacchi + current_fibonacchi)

  # term_nが1になるまで再帰呼び出し
  # prev_fibonacchiとcurrent_fibonacchiは配列の後ろ2つ
  calc_fibonacchi(term_n - 1, $fibonacchi_array[-2], $fibonacchi_array[-1])
end

# 求めたい項数を入力
puts "フィボナッチ数列の第n項を求めます"
print "nをいくつにしますか？ : "
n = gets.to_i

# 第n項のフィボナッチ数列の数を求める
fibonacchi_n = calc_fibonacchi(n)

# 答えを表示
puts "フィボナッチ数列の第#{n}項の数は#{fibonacchi_n}です"

結果

フィボナッチ数列の第n項を求めます
nをいくつにしますか？ : 10
フィボナッチ数列の第10項の数は55です