再帰を使ったFibonacci数列

Fibonacci数列

Fibonacci数列とは

fib(n) = fib(n-1)+fib(n-2)                                                  
0 1 1 2 3 5 8 13 21 ...                                                     

で表される* どの数字も前２つの数字を足した数字 *という規則を持つ数列です．
これを今回は再起を用いて解きます．

方法

Rubyの基礎2で作ったassert_equal.rbを利用してfibonacci.rbを作っていきます.

初項

Fibonacci数列の初項は0です．

• まずは表示させてみます．

  p fib(0)                                                                      
  

もちろんありません．

• defします．

  def fib(n)                                                                    
    if n==0                                                                     
      return 0                                                                  
    end                                                                         
  end                                                                           
  

• assert_equal.rbを呼び出して，出力を確認してみます.

require './assert_equal'                                                      
puts assert_equal(0, fib(0))                                                  

$ ruby fibonacci.rb
expected :: 0                                                                 
result   :: 0                                                                 
succeeded in assert_equal.                                                    

もちろん0しか返されないのでtrueです．

第二項

次はfib(1)=1，初項と同様にやっていきます．
n=1の時をdefに追加

def fib(n)                                                                    
  if n==0                                                                     
    return 0                                                                  
  end                                                                         
  if n==1                                                                     
    return 1                                                                  
  end                                                                         
end                                                                           

テスト用のputsはこんな感じ

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

• テストを配列に入れてみた方がきれいな感じがする.

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

以降

これ以降はfib(n) = fib(n-1)+fib(n-2)を使っていきます．0と1でない値の時にreturnできるようにします．
defに追加，テストには第三項を追加

require './assert_equal'

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|
  assert_equal(expected), fib(index))
end

出力してみる

$ ruby fibanacci.rb
expected :: 0
result   :: 0
succeeded in assert_equal.
expected :: 1
result   :: 1
succeeded in assert_equal.
expected :: 1
result   :: 1
succeeded in assert_equal.

全てtrueなのでいい感じ

テストを追加

追加後のプログラムはこんな感じ

require './assert_equal'

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],[3,2],[4,3],
[5,5],[6,8],[7,13],[8,21],].each do |index, expected|
  assert_equal(expected), fib(index))
end

完成．終わり

---

• source ~/Desktop/grad_members_20f/members/mm-cell/post_org/fibonacci.org