第十回：再帰

目標

フィボナッチ数列を求めるコードの作成を行う．

フィボナッチ数列とは，n項=(n-1)項+(n-2)項となるもの．0,1,1,2,3,5,8,13,21 …となる．

n=0の時

0項目は0となるので，以下のようにコーディングする．

require './assert_equal.rb'
def fib(n)
  if n==0
     return 0
  end
end

puts assert_equal(0,fib(0))

require './assert_equal.rb'

によって，前回作成したassert_equal.rbを呼び出している．

これを実行すると，

$ ruby fibonacci.rb
true

となる．

n=1の時

1項目は1となるので，以下のように追加する．

require './assert_equal.rb'
def fib(n)
  if n==0
     return 0
  end
  if n==1
     return 1
  end
end

puts assert_equal(0,fib(0))
puts assert_equal(1,fib(1))

これを実行すると以下のようになる．

$ ruby fibonacci.rb
true

true

n=2の時

2項目は1となるので，以下のように変更する．

require './assert_equal.rb'
def fib(n)
  if n==0
     return 0
  end
  if n<=2
     return 1
  end
end

puts assert_equal(0,fib(0))
puts assert_equal(1,fib(1))
puts assert_equal(1,fib(2))

コードが長くなってきたので，if文を短くして，puts assert_equalの部分を配列にする．

requrire './assert_equal.rb'
def fib(n)
  return 0 if n==0
  return 1 if n<=2
end

[[0,0],[1,1],[2,1]].each do |index, expected|
  puts assert_equal(expected, fib(index))

n=3以降の時

3項目以降は，2項目以前が値が決まっているので，以下のように変更する．

requrire './assert_equal.rb'
def fib(n)
  return 0 if n==0
  return 1 if n==1
  return fib(n-1) + fib(n-2)
end

[[0,0],[1,1],[2,1]].each do |index, expected|
  puts assert_equal(expected, fib(index))

2項目も0項目+1項目で求められるので，n<=2をn==1に変更してある．これでフィボナッチ数列を求められる．

参考サイト

参考にしたサイトは以下の通り．

• https://qiita.com/daddygongon/items/1bb27b8920c201d5c520

---

• source ~/grad_members_20f/members/yuhsuzu/r10.org